高效的不经意传输协议黄根勋，朱健东（解放军信息工程大学理学院，河南郑州，450001）(Email-zjd19820706sohu.com)摘要： 不经意传输协议作为密码学的基础协议，在实际生活中有很多应用，例如个人信息的恢复(PIR)，不经意抽样(OS)，公平的电子合同的签订等等。衡量一个不经意传输协议优劣的一个重要的指标就是其计算复杂度，因而如何降低不经意传输协议的计算复杂度是研究的重点。本文是在1方案的基础上，给出了两个计算上更简单的协议。关键词：不经意传输；个人信息恢复； 和一致生成器；计算复杂度 Oblivious Transfer Protocol with high efficiencyHuang Genxun，Zhu Jiandong(College of science, Information Engineering University, Zhengzhou, 450001)Abstract: As a fundamental cryptology protocol，oblivious transfer has different application in real life. For example， the private information retrieval(PIR for short)，oblivious sampling and the signing of fair electronic contract etc. Computation complexity is a very important criterion to decide whether a oblivious transfer protocol is better or not，so the research keystone of oblivious transfer is how to reduce computation complexity. The thesis put forward two protocols with lower computation complexity based on 1.Keywords: oblivious transfer；Private Information Retrieval；sum consistent synthesizer；computation complexity1引言不经意传输协议(OT)是一个由发送方Bob和接收方Alice参与的双方协议.发方Bob有n个输入， ，执行完协议之后Alice得到其中的一个，但Bob不知道是哪一个。1.1不经意传输简介1985年首先由Even，Goldreich和Lempel在2提出，它是对Rabin的“不经意传输”3的推广( 实际上在七十年代这个概念Wiesner已经提出，但是直到4才被正式发表出来)。Brassard，Crpeau和Robert在9中再次将Rabin的不经意传输做出了推广，提出了的概念。定义1(Rabin的不经意传输):Bob知道一个秘密，想以1/2的概率传递给Alice，即Alice以1/2的概率得到这个秘密，但Bob并不知道Alice是否得到这个秘密。定义2()Bob有两个秘密，想将其中之一交给Alice，即Alice得到一个秘密，但Bob不知道Alice得到了哪一个。定义3()Bob有n个秘密，想将其中之一交给Alice，Alice得到一个秘密，但Bob不知道Alice得到的是哪一个。平行的执行k次，就是一个协议。Wen-Guey Tzeng在5中指出了构造的方法有两种：第一种是首先构造，然后执行多轮来实现。例如6就是采用这个方法；第二种是直接通过密码学基础技术构造，5本身就是这种协议。一般看来，直接构造的方法往往计算复杂度较大，达到O(n)，通常的做法是先把转化为若干个（mn）。Moni Noar和Beny Pinkas在1中把转化成个，使得它的计算复杂度降低到O()，而本文将把它进一步转化成q个，其中.由于q是可变的，我们可以选择最佳的q使得计算复杂度最小。在1中为了避免执行过程中的过多的指数模运算， Moni Naor和Benny Pinkas引入了和一致生成器的概念。我们将利用和一致生成器给出一个方案，把转化成3q个，。这样我们也可以选择最佳的q使得计算复杂度最小。2预备知识2.1 的安全性和计算复杂度是一个双方协议，分为初始化和传输两个阶段。考虑到发送者可能在传输的过程中改变消息的内容，要求Bob在消息传输前进行预处理，即在初始化阶段他用n个密钥对n个消息处理，然后把处理的结果全部发给Alice。传输阶段Alice首先选择i:，然后与Bob执行若干次（tn），获得密钥，进而获得。安全性 协议的安全性从发方和收方两个角度考虑：1. 发方的安全性：在执行完t-1轮 协议之后，接收者不能获得除t-1条消息之外的其他消息的任何信息；2. 收方的安全性：发送者执行完协议之后，不知道接受者获得了哪个消息。计算复杂度 发方和收方分别作指数模运算的次数。2.2 应用背景一个效率高的协议，在现实应用中可以减少通信双方的计算量。不经意传输协议的一个基本应用是个人信息恢复(Private Information Retrieval)。定义4 ：PIR 一个用户想从一个数据库中查询自己感兴趣的消息，但他不想让数据库的管理者知道他查询的是什么，这样他们之间需要一个PIR协议。通常PIR协议不限制用户从数据库中获得的消息数，与相比，它不保护发送者的安全性。如果一个PIR能与OT结合起来，保护发方的隐私，那么它就变成一个SPIR(Symmetric Private Information Retrieval) 。PIR和还有一个区别就是PIR侧重减少通信量，而OT侧重减少计算量。在实际通信中，应更多地考虑计算机的数据处理能力，鉴于指数模运算的相对困难性，我们更侧重于减少计算量。2.3 和一致生成器Moni Naor和Benny Pinkas在1中为了避免执行过程中的过多的指数模运算，引入了和一致生成器的概念。定义5 ：(和一致生成器) 一个有个输入变量函数S称为和一致生成器，如果它满足下面的性质:1. S是一个伪随机生成器；2.，和，满足条件：=，则： S(，)=S(，)3不经意传输协议方案1 设Bob有n个消息，Alice想通过不经意传输得到它们中的一个。将n个消息对应到一个q维矩阵. i1，2，n ，i表示成，其中1，2，t ，n=，j=1，2，q，并设g是有限域上的本原元。一.初始化：1. Bob随机的选择q个数组：，生成密钥=，得到= ()；2.Bob把，全部交给Alice。二传输阶段：1. Bob随机的选择q个数，分别用来随机化上述的q个数组，得到:（），；2.对于j=1，2，q，Alice和Bob执行q次协议，如果Alice的选择i能表示成，那么Alice得到，j=1，2，q；3.Bob把发给Alice.4.Alice恢复密钥，得到，。定理1 方案1中协议双方都是安全的。证明：该方案实际上是把一个协议转化成q个协议，而保证了它的安全性.计算复杂度分析：该方案中，Bob在初始化阶段做了n次指数模运算，然后双方执行q次协议，最后Alice再做一次指数模运算.方案的优点:该方案的计算复杂度在很大程度上取决于具体的的计算复杂度.Wen-Guey Tzeng在5中的一个需发方做2n次指数模运算，收方做2次指数模运算.如果我们先用上述方案把转化成q个（n=），再采用5的方案执行，这样发方需做n+2qt+1次指数模运算，收方需做2q+1次指数模运算，我们发现t=3是最佳的。实际上在这个方案中，我们可以视具体的协议选择最佳的q使得计算复杂度最小，而1的方案只是把一个转化成个，这正是本方案对1的方案改进的地方。 n条消息编号为并将它们写成t进制，其中，则每条消息的编号可以由q位数表示它。，。取素数p使得(p，n)=1， ，和k也用t进制表示，。定义向量=，有3qt个坐标，这些坐标由和k的t进制表示确定。的坐标从首至尾每t个称为一个区域.共有3q个区域，每个区域的坐标只有一个为1，其他全部为0。我们认为这样得到的的坐标是随机的。设有s+1个极小线性相关的向量，即这s+1个向量在某个坐标要么全部为0，要么至少有2个向量在这个坐标上取1，因此这s+1个向量在每个区域中1至多集中在个坐标上.鉴于坐标分布的随机性，每个区域中1至多集中在个坐标上的概率不超过，这种性质保持在3q个区域上的概率小于。同理，存在+1（s）个极小线性无关的向量的概率小于，而存在s+1个线性相关的向量的概率是存在+1个极小线性相关的向量的概率之和。当s相对于适当地小，例如：当10000，时，100，存在10个极小线性相关的向量的概率小于，进一步可以估算出存在个线性相关的向量的概率非常小。方案2 n条消息编号为并将它们写成t进制，其中，则每条消息可以由q位数表示它.，。取素数p使得（p，n）=1，和k也用t进制表示，。一初始化：1. Bob随机的选择3q个数组，共3qt个数。 1，2，n ，表示成，算出的表示，的表示。密钥=S(，)， 由此得到 =()。2.Bob把，全部交给Alice。二传输阶段：1.Bob随机的选择3q个数：，分别用来随机化上述的3q个数组，它们的和为0。2.Alice和Bob执行3q次协议，如果Alice的选择表示成，算出的表示，的表示，Alice得到，j=1，2。3.Alice 恢复密钥: ，得到。引理1 已知s条消息不能得到s+1条消息，当且仅当上述的任意s+1个向量线性无关。 证明：不妨假设Alice已经得到了s条消息的编号是，她现在想的得到第s+1条消息.若（*），而完全决定了在协议中要得到哪些随机数。例如，而=。则协议中要得到，j=1，2，（这里我们要注意，每执行一次协议就要重新选取随机数，因而每一轮是不相同的）。我们用反映协议中接受者要得到的随机数，=由（*）得到，记作。的坐标中的非零元素对应着一些随机数。不妨假设=记=的非零坐标就是初始化阶段生成第条消息的密钥的各随机数，由于我们前面执行的s次协议的传输阶段所取的3q个随机数之和为零，因此的坐标中的非零元素恰好等于非零元素之和，再由和一致生成器的性质，很容易由得到第条消息。另一方面如果我们从前面得到的s条消息所获得的随机数组，得到了第条消息的密钥，由于协议中得到的随机数都是经过另一些随机数隐藏了的，并不是初始化时生成密钥的随机数组，不能单独处理，因此可以证明可以由线性表出。综上所述当且仅当任意s+1个向量线性无关时，已知s条消息，不能得到s+1条消息。定理2当s适当地小于时，接收方在得到s条消息后，再想得到一条消息的概率非常小。证明：当s适当地小于时，前面所述的任意s+1个向量为线性相关组的概率非常小，即这s+1个向量线性无关的概率接近.由引理1知，结论显然成立。计算复杂度分析： 该方案采用和一致生成器生成密钥，然后将转化成3q个协议。该方案的计算复杂度取决于具体的协议的计算复杂度，因此我们可以合理的选择q，使得计算复杂度最小。由于，而本方案要求s适当地小于，所以基于安全性考虑，不宜过大。4.小结文中提出的两个方案都是将转化成若干个协议(tn