文档介绍：:.. 高效的不经意传输协议黄根勋,朱健东(解放军信息工程大学理学院,河南郑州,450001)(Email-z)摘要:不经意传输协议作为密码学的基础协议,在实际生活中有很多应用,例如个人信息的恢复(PIR),不经意抽样(OS),公平的电子合同的签订等等。衡量一个不经意传输协议优劣的一个重要的指标就是其计算复杂度,因而如何降低不经意传输协议的计算复杂度是研究的重点。本文是在[1]方案的基础上,给出了两个计算上更简单的协议。关键词:不经意传输;个人信息恢复;和一致生成器;计算复杂度ObliviousTransferProtocolwithhighefficiencyHuangGenxun,ZhuJiandong(Collegeofscience,InformationEngineeringUniversity,Zhengzhou,450001)Abstract:Asafundamentalcryptologyprotocol,,theprivateinformationretrieval(PIRforshort),plexityisaveryimportantcriteriontodecidewhetheraoblivioustransferprotocolisbetterornot,[1].Keywords:oblivioustransfer;PrivateInformationRetrieval;(OT),,,执行完协议之后Alice得到其中的一个,但Bob不知道是哪一个。,Goldreich和Lempel在[2]提出,它是对Rabin的“不经意传输”[3]的推广(实际上在七十年代这个概念Wiesner已经提出,但是直到[4]才被正式发表出来)。Brassard,Crépeau和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-GueyTzeng在[5]中指出了构造的方法有两种:第一种是首先构造,然后执行多轮来实现。例如[6]就是采用这个方法;第二种是直接通过密码学基础技术构造,[5]本身就是这种协议。一般看来,直接构造的方法往往计算复杂度较大,达到O(n),通常的做法是先把转化为若干个(m<n)。MoniNoar和BenyPinkas在[1]中把转化成个,使得它的计算复杂度降