一个高效可完全模拟的n取1茫然传输协议

魏晓超 蒋 瀚 赵 川

(山东大学计算机科学与技术学院 济南 250101)(weixiaochao2008@163.com)



一个高效可完全模拟的n取1茫然传输协议

魏晓超 蒋 瀚 赵 川

(山东大学计算机科学与技术学院 济南 250101)(weixiaochao2008@163.com)

茫然传输；全模拟；判定DDH假设；安全两方计算；双模式加密系统

近年来，网络信息的大量收集引发了人们对信息安全与隐私的广泛专注.密码学者们提出了许多可以避免信息泄露的密码学方案，诸如安全多方计算(secure multi-party computation, SMPC)、隐私信息检索(private information retrieval, PIR)等.在这些协议的具体实现中，茫然传输(oblivious transfer, OT)作为一个密码学基础工具，是协议构造过程中不可或缺的重要组成部分.

一个具体的例子，我们最熟悉的网络搜索引擎，如百度、谷歌等，都需要搜索信息的用户输入自己要搜索的明文信息，然而当所搜索的信息涉及到重要隐私时，用户的隐私会面临重大危害.假设搜索者在能得到所需信息的同时，又能不泄露自己的搜索信息，则用户的隐私性就得到了大大的保护.这也正是OT协议所要实现的目的之一.

OT协议作为安全两方计算(secure two-party computation, STPC)的一种实例，其安全性可以使用文献[2,8-9]所给出的安全多方计算的安全性定义来形式化描述，即理想现实模拟范式(idealreal simulation paradigm).在这样一种范式中，存在理想世界(ideal eorld)和现实世界(real world)两种场景.在理想世界中，有一个完全可信的第三方，其接收参与方的输入并计算某些功能函数(functionality)，然后将相关输出信息返回给参与方；与此不同，在现实世界中，参与方不借助可信第三方的帮助，他们之间通过交互式地运行某些协议来得到相应的输出结果.一个现实世界中的协议如果说是安全的，当且仅当没有敌手能在现实世界中作出比理想世界更多的恶意行为.这可以表示为，对任意在现实世界中执行了一个成功攻击的敌手，总存在一个理想世界的敌手也能够成功执行相同的攻击.为了形式化定义上述安全性，我们比较一个敌手在现实世界中与一个诚实参与方的联合输出分布(joint output distribution)，以及在有可信第三方存在的理想世界中的联合输出分布.如果以上2种世界中的联合输出分布是计算不可区分的，则说明该协议是安全的.根据不同的安全性需求，文献[2]针对OT协议给出了3种安全性定义，即只保证隐私性(privacy only)、单边模拟(one-sided simulation)以及完全模拟(full simulation)，其中完全模拟较之于前两者安全性更高，设计能实现完全模拟的OT协议也更困难.

1 相关工作和主要结论

1.1 相关工作

1.2 本文的主要工作

2 基本知识和定义

2.1 1-out-of-n茫然传输

输入: S输入n个值(x1,x2,…,xn)∈{0,1}n，R输入1个值σ∈{1,2,…,n}；

输出: R输出xσ.

2.2 批量DH元组的知识的零知识证明

给定一个q阶群G，其生成元是g,h，且q为素数.我们说群G上的一个四元组(g,h,u,v)是一个DH元组，当且仅当存在一个值w满足u=gw且v=hw；反之，则称该元组为非DH元组.

DH元组知识的零知识证明旨在证明给定一个元组是DH元组，换言之，即证明关系

RDH={(G,q,g0,g1,h0,h1)},

其中，G，q如上所述；g0,g1是生成元，且存在一个证据w满足h0=(g0)w,h1=(g1)w.

上述单一DH元组知识的零知识证明协议，在文献[2-3]中已经给出，在我们的协议中用到的是对该协议的一个扩展，即证明多个元组均为DH元组，且对应的证据w相同.具体地，我们要证明如下关系：

RDH={(G,q,(g0,h0),(g1,h1),…,(gn,hn))}，

其中,G，q如上所述；g0,g1,…,gn是生成元，且存在唯一的证据w满足h0=(g0)w,h1=(g1)w,…,hn=(gn)w.

我们可以证明(g0,h0,g1,h1),(g0,h0,g2,h2),…,(g0,h0,gn,hn)都是DH元组，且每个DH元组的证据相同.然而，注意到以上n个元组中(g0,h0)是公共的，因此我们可以将所有的证明归结到一个证明中去，即证明(g0,h0)和另外其他n个元素对(g1,h1),(g2,h2),…,(gn,hn)的任一随机线性组合形式(g′,h′)组成一个DH元组，其中g′=(g1)a1×(g2)a2×…×(gn)an,h′=(h1)a1×(h2)a2×…×(hn)an，a1,a2,…,an∈q.不难看出，如果要满足四元组(g0,g′,h0,h′)是一个DH元组，即存在一个证据w满足h0=(g0)w,h′=(g′)w，则必然要满足h1=(g1)w,h2=(g2)w,…,hn=(gn)w.具体协议描述如下:

协议1. 批量DH元组的知识的零知识证明协议.

公共输入：证明者P和验证者V共同拥有输入R={(G,q,(g0,h0),(g1,h1),…,(gn,hn))}，其中群G的阶为素数q，生成元为g0，其他为群G中的元素；

证明者P的辅助输入：P拥有一个证据w满足h0=(g0)w,h1=(g1)w,…,hn=(gn)w.

协议：

步骤1.P随机选择值a∈{1,2,…,q}，并计算α=(g0)a，然后将α发送给V.

步骤2.V随机选择值s,t，a1,a2,…,an∈{1,2,…,q}，并计算c=(g0)s×αt和g′=(g1)a1×(g2)a2×…×(gn)an，然后将c和g′发送给P(这是对c的完美隐藏承诺，且a1,a2,…,an是某随机线性组合的系数).

步骤3.P随机选择值r∈{1,2,…,q}，并计算A=(g0)r和B=(g′)r，然后将(A,B)发送给V.

步骤4.V将s,t发送给P.

步骤5.P验证是否c=(g0)s×αt，如果不成立则中止;否则，P计算z=s×w+r，然后将z和a(在步骤1中所选)发送给V.

步骤6.V验证以下是否成立：

1)α=(g0)a；

上述协议需要5轮交互，参与者交换9个群元素(其中P发送5个，V发送4个).此外，参与者共计算2n+12次指数运算(其中P计算5个，V计算2n+7个).

2.3RAND函数

RAND函数是定义在群G上的一个映射函数.给定一个q阶群G，其生成元是g.定义函数RAND(w,x,y,z)=(u,v)，满足u=(w)s×(y)t且v=(x)s×(z)t，其中s,t∈q.RAND函数有以下性质：

声明1. 令G为一个q阶群，其生成元是g，且w,x,y,z∈G.如果元组(w,x,y,z)是一个DH元组，即存在某个值α满足x=wα,z=yα，则对于(u,v)←RAND(w,x,y,z)满足v=uα;相反，如果元组(w,x,y,z)不是一个DH元组，则(u,v)←RAND(w,x,y,z)就是群G中的2个随机元素，即如下2个分布(w,x,y,z,RAND(w,x,y,z))和(w,x,y,z,gα,gβ)是相同的，其中α,β∈q.

2.4 安全性定义

1) 计算不可区分性.如果说2个分布总体X={X(a,n)}a∈{0,1}*;n∈和Y={Y(a,n)}a∈{0,1}*;n∈是计算不可区分的，表示为X≡Y.需要满足当对每个非均匀多项式时间算法D总存在一个可忽略函数μ(·)，对于每个a∈{0,1}*和每个n∈，有:

|Pr[D(X(a,n)=1)]-Pr[D(Y(a,n)=1)]|≤μ(n).

2) 完全模拟的安全性定义.恶意敌手模型下两方计算的安全性定义主要基于理想/现实模拟范例.文献[2]给出了形式化定义如下：

定义1. 令f:{0,1}*×{0,1}*→{0,1}*×{0,1}*是一个两方功能函数，π是一个真实的两方协议.若协议π在恶意敌手模型下安全计算f，必须满足针对现实模型中的每个非均匀概率多项式时间敌手A，总存在一个理想模型中的非均匀概率多项式时间敌手S，对于每个i∈{1,2}，

{IDEALf,S(z),i(x,y,z,n,s)}≡

{REALπ,A(z),i(x,y,z,n,s)}，

其中x,y,z∈{0,1}*满足|x|=|y|，且n,s∈.

3 n取1茫然传输协议

3.1n取1茫然传输协议

在本节中，我们给出一个标准恶意敌手模型下可以完全模拟的n取1茫然传输协议.协议的主要思想是让接收方构造n个四元组，满足仅有一个元组符合DH元组属性.为了阻止参与方的恶意行为，我们引入知识的零知识证明技术.协议具体表述如下:

输入:S输入n个值(x0,x1,…,xn-1)∈{0,1}n，R输入1个值σ∈{0,1,…,n-1}；

辅助输入: 安全参数n，以及一个q阶群G，其生成元为g0；

输出:R输出xσ.

协议：

步骤1.R随机选择y1,y2,…,yn-1,α∈q，并计算(g1=(g0)y1,g2=(g0)y2,…,gn-1=(g0)yn-1),以及(h0=(g0)α,h1=(g1)α+1,…,hn-1=(gn-1)α+n-1);然后将(h0,(g1,h1),…,(gn-1,hn-1))发送给S.

步骤2.R使用知识的零知识证明系统向S证明存在一个值α，满足：

步骤3. 接收方R随机选择一个值r∈q，并计算g=(gσ)r,h=(hσ)r，然后将(g,h)发送给S.

步骤4.S按如下方式操作：

① 定义函数RAND(w,x,y,z)=(u,v)，其中u=(w)s×(y)t，v=(x)s×(z)t，且s,t∈q.

② 针对任意i=0,1,…,n-1，发送方S计算(ui,vi)=RAND(gi,g,hi,h)，然后计算wi=vi×xi，并将(ui,wi)发送给R.

3.2 协议正确性分析

如果协议双方都诚实按照协议执行，可以保证R只得到xσ.我们分别针对i=σ以及i≠σ这2种情况分析上述协议的正确性.

1) 针对i=σ，元组(gi,g,hi,h)=(gi,(gi)r,hi,(hi)r)是DH元组.因此我们有：

2) 针对任一i≠σ，元组(gi,g,hi,h)=(gi,(gσ)r,hi,(hσ)r)全是非DH元组，因此:

3.3 协议形式化证明

直观地说，因为接收方R要通过知识的零知识证明系统向发送方S证明其构造的四元组满足要求，所以R只能得到参与方输入的某一个值，因此除了这个值以外的其他输入值对于R来说依然是保密的.考虑R的输入隐私性，因为群上的DDH问题是困难的，所以接收方S不能判断哪一个元组是DH元组，从而也就不知道R的选择什么.以下我们将根据2.4节的安全性定义给出协议的形式化证明.

证明. 我们在混合模型下证明上述协议的安全性，其中知识的零知识证明被一个理想功能函数计算.证明分为S被腐化和R被腐化这2种情况.

1)S被腐化.令A为现实世界的敌手，其控制发送方S.我们构造一个模拟器SSEND调用敌手A的输入，并作如下操作：

步骤1. SSEND随机选择y1,y2,…,yn-1,α∈q，并像诚实的接收方R一样计算g1=(g0)y1,g2=(g0)y2,…,gn+1=(g0)yn+1;然后设置(h0=(g0)α,h1=(g1)α,…,hn-1=(gn-1)α)，这一点是与诚实接收方R不同的;最后SSEND将(h0,(g1,h1),…,(gn-1,hn-1))发送给A.

步骤2. SSEND模拟知识的零知识证明系统的理想功能函数，并把1输送给敌手A，这意味着接收方R的零知识证明通过验证.

步骤3. SSEND随机选择一个值r∈q并计算g=(gσ)r,h=(hσ)r，然后将(g,h)发送给A.

步骤4. 收到A发送的(u0,w0),(u1,w1),…,(un-1,wn-1)，模拟器SSEND像诚实的R一样计算所有的值(x0,x1,…,xn-1);然后将这些值发送给计算茫然传输协议的功能函数，并输出敌手A输出的内容，然后中止.

以上是S被腐化的理想模拟过程.我们要证明在理想世界中模拟器SSEND和一个诚实的接收方R执行的联合输出分布，与敌手A和诚实的R在现实协议中产生的输出联合分布计算不可区分，即

注意到以上理想模拟过程与现实协议的唯一不同是协议步骤中(h0,h1,…,hn-1)的构造方式.在理想模拟中，模拟器SSEND错误构造(h0,h1,…,hn-1)，使得所有的元组(g0,g,h0,h),(g1,g,h1,h),…,(gn-1,g,hn-1,h)都是DH元组.但是在现实协议中，只有唯一的1个元组(gσ,g,hσ,h)是DH元组，而其他元组均是非DH元组.假设以上2个输出联合分布能以不可区分的概率被区分开来，则一定存在一个区分器D以相同的概率区分一个DH元组和一个非DH元组，然而这与群上的DDH问题是困难的相矛盾，因此上述IDEAL分布和HYBRID分布是计算不可区分的.

2)R被腐化. 令A为现实世界的敌手，其控制接收方R.我们构造一个模拟器SREC调用敌手A的输入，并作如下操作：

步骤1. 模拟器SREC从敌手A处接收到值(h0,(g1,h1),…,(gn-1,hn-1),(g,h))，并像诚实的发送方S一样验证零知识证明.

① 如果验证失败，SREC发送⊥至计算茫然传输功能函数的可信第三方，并中止协议.

② 否则，SREC运行零知识证明的抽取器，抽取出证据α.然后，对于i=0,1,…,n-1，SREC计算(g)α+i并与h比较，将与h相等的值i设置为敌手A的真实输入σ.

步骤2. SREC将敌手A的真实输入σ发送给计算茫然传输功能函数的可信第三方，并得到值xσ.

步骤3. SREC使用步骤2中得到的值xσ，像一个诚实发送方S一样正确计算(uσ,wσ).而对于那些索引i≠σ，SREC设置(ui,wi)为群G中的任意元素.最后SREC将这些值(u0,w0),(u1,w1),…,(un-1,wn-1)发送给敌手A，输出敌手A输出的内容，并中止协议.

以上是R被腐化的理想模拟过程.注意到在上述协议中，发送方S并没有输出，因此我们只需要证明在理想世界中敌手A和模拟器SREC执行的输出分布，与敌手A和诚实的S在现实协议中产生的输出分布是计算不可区分的，即

通过比较IDEAL和HYBRID的执行过程，唯一的不同就是对于那些索引i≠σ，值(ui,wi)的生成方式.在理想模拟中，这些值是模拟器SREC从群G中随机选取的群元素；而在现实协议中，这些值是由诚实的发送方S使用RAND函数计算而得的.因为对于任意i≠σ，元组(gi,g,hi,h)都不是DH元组.根据RAND函数的性质，使用非DH元组计算所得的值在群G中是独立随机的，因此在理想模拟和现实协议中这些值是计算不可区分的.鉴于此，我们推出上述理想模拟和现实协议的输出分布是不可区分的.

综上所述，我们完成对定理1的证明.

证毕.

3.4 协议效率分析与比较

我们主要从3个方面针对上述协议的效率作出分析：

1) 交互轮数. 上述协议共需要6轮交互，其中包括零知识证明的交互轮数.

2) 本地指数计算量. 除去零知识证明协议中的计算量，在上述协议中发送方S和接收方R分别计算4n和2n+2次指数操作.加上零知识证明子协议中的2(n-1)+12次，协议的总指数计算量是8n+12.

3) 带宽. 除去零知识证明协议中参与方的通信量，在上述协议中发送方S和接收方R分别发送2n和2n+1个群元素.加上零知识证明协议中共发送的9个群元素，协议的总带宽为4n+10.

表1是我们的协议与已有的部分n取1茫然传输协议的对比结果.其中,文献[12-14]中的协议不能在标准恶意敌手模型下被全模拟，而我们的协议可以实现全模拟，所达到的安全性更强；方案[16,18]中的协议虽然能达到UC安全这样一种更强的安全性，但是其协议需要公共参考串的存在，且方案[18]中的协议复杂度为O(nlogn)，而我们的协议是在标准模型下安全的，不需要公共参考串的存在，且复杂度仅与n线性先关.

Table 1 Comparison of 1-out-of-n Oblivious Transfer Protocols

4 结束语

2) 在更为复杂的安全模型下，如UC模型、自适应模型等，设计更为高效的茫然传输协议.

[1]Rabin M O. How to exchange secrets by oblivious transfer, TR-81[R]. Cambridge, MA: Harvard University, 1981

[2]Hazay C, Lindell Y. Efficient Secure Two-Party Protocols: Techniques and Constructions[M]. Berlin: Springer, 2010

[3]Lindell Y, Pinkas B. Secure two-party computation via cut-and-choose oblivious transfer[G] //LNCS 6597: Advances in TCC 2011. Berlin: Springer, 2011: 329-346

[4]Yao A. How to generate and exchange secrets[C] //Proc of the 27th IEEE Symp on Foundations of Computer Science (FOCS1986). Los Alamitos, CA: IEEE Computer Society, 1986: 162-167

[5]Lindell Y, Pinkas B. An efficient protocol for secure two-party computation in the presence of malicious adversaries[G] //LNCS 4515: Advances in Cryptology—EUROCRYPT 2007. Berlin: Springer, 2007: 52-78

[6]Qu Yadong, Hou Zifeng, Wei Wei. A protocol for signing contracts based on oblivious transfer[J]. Journal of Computer Research and Development, 2003, 40(4): 615-619 (in Chinese)

(曲亚东, 侯紫峰, 韦卫. 基于不经意传输的合同签订协议[J]. 计算机研究与发展, 2003, 40(4): 615-619)

[7]Even S, Goldreich O, Lempel A. A randomized protocol for signing contracts[J]. Communications of the ACM, 1985, 28(6): 637-647

[8]Goldreich O. Foundations of Cryptography: Volume 2—Basic Applications[M].Cambridge, UK: Cambridge University, 2004

[9]Goldreich O, Micali S, Wigderson A. How to play any mental game—A completeness theorem for protocols with honest majority[C] //Proc of the 19th Annual ACM Symp on Theory of Computing. New York: ACM, 1987: 218-229

[10]Brassard G, Crepeau C, Robert J M. All-or-nothing disclosure of secrets[G] //LNCS 263: Advances in Cryptology—CRYPTO 1986. Berlin: Springer, 1986: 234-238

[11]Stern J P. A new and efficient all-or-nothing disclosure of secrets protocol[G] //LNCS 1514: Advances in Cryptology—Asiacrypt 1998. Berlin: Springer, 1998: 357-371

[12]Naor M, Pinkas B. Efficient oblivious transfer protocols[C] //Proc of the 12th Annual ACM-SIAM Symp on Discrete Algorithms (SODA). New York: ACM, 2001: 448-457

[13]Aiello B, Ishai Y, Reingold O. Priced oblivious transfer: How to sell digital goods[G] //LNCS 2045: Advances in Cryptology—EUROCRYPT 2001. Berlin: Springer, 2001: 119-135

[14]Tzeng W. Efficient 1-out-of-noblivious transfer schemes[C] //Proc of the Public-Key Cryptography (PKC 2002). Berlin: Springer, 2002: 159-171

[15]Lindell Y. Efficient fully-simulatable oblivious transfer[C] //Proc of Cryptographers’ Track—RSA 2008. Berlin: Springer, 2008: 52-70

[16]Peikert C, Vaikuntanathan V, Waters B. A framework for efficient and composable oblivious transfer[G] //LNCS 5157: Advances in Cryptology—CRYPTO 2008. Berlin: Springer, 2008: 554-571

[17]Zhang Bin, Xu Qiuliang, Jiang Han. Novel composable oblivious transfer protocol against adaptive adversary[J]. Journal on Communications, 2011, 32(11A): 241-247 (in Chinese)

(张斌, 徐秋亮, 蒋瀚. 新的可抵抗自适应敌手的可组合茫然传输协议[J]. 通信学报, 2011, 32(11A): 241-247)

[18]Garay J A, Ishai Y, Kumaresan R, et al. On the complexity of UC commitments[G] //LNCS 8441: Advances in Cryptology-EUROCRYPT 2014. Berlin: Springer, 2014: 677-694

Wei Xiaochao, born in 1990. PhD candidate. His main research interests include secure multiparty computation and search on encrypted data.

Jiang Han, born in 1974. PhD and lecturer. His main research interests include theory of cryptography, side-channel attacks and cryptographic protocols.

Zhao Chuan, born in 1989. PhD. His main research interests include secure multiparty computation and search on encrypted data (zhaochuan.sdu@gmail.com).

An Efficient 1-out-of-nOblivious Transfer Protocol with Full Simulation

Wei Xiaochao, Jiang Han, and Zhao Chuan

(SchoolofComputerScienceandTechnology,ShandongUniversity,Jinan250101)

oblivious transfer (OT); full simulation; decisional Diffie-Hellamn (DDH) assumption; secure two-party computation (STPC); dual-mode cryptosystem

2015-06-12；

2016-02-03

国家自然科学基金项目(61173139)； 教育部高等学校博士学科点专项科研基金项目(20110131110027)

蒋瀚(jianghan@sdu.edu.cn)

TP301

This work was supported by the National Natural Science Foundation of China (61173139) and the Specialized Research Fund for the Doctoral Program of Higher Education of China (20110131110027).