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