魏曉超 蔣 瀚 趙 川

(山東大學計算機科學與技術學院 濟南 250101)(weixiaochao2008@163.com)

?

一個高效可完全模擬的n取1茫然傳輸協(xié)議

魏曉超 蔣 瀚 趙 川

(山東大學計算機科學與技術學院 濟南 250101)(weixiaochao2008@163.com)

茫然傳輸；全模擬；判定DDH假設；安全兩方計算；雙模式加密系統(tǒng)

近年來，網(wǎng)絡信息的大量收集引發(fā)了人們對信息安全與隱私的廣泛專注.密碼學者們提出了許多可以避免信息泄露的密碼學方案，諸如安全多方計算(secure multi-party computation, SMPC)、隱私信息檢索(private information retrieval, PIR)等.在這些協(xié)議的具體實現(xiàn)中，茫然傳輸(oblivious transfer, OT)作為一個密碼學基礎工具，是協(xié)議構造過程中不可或缺的重要組成部分.

一個具體的例子，我們最熟悉的網(wǎng)絡搜索引擎，如百度、谷歌等，都需要搜索信息的用戶輸入自己要搜索的明文信息，然而當所搜索的信息涉及到重要隱私時，用戶的隱私會面臨重大危害.假設搜索者在能得到所需信息的同時，又能不泄露自己的搜索信息，則用戶的隱私性就得到了大大的保護.這也正是OT協(xié)議所要實現(xiàn)的目的之一.

OT協(xié)議作為安全兩方計算(secure two-party computation, STPC)的一種實例，其安全性可以使用文獻[2,8-9]所給出的安全多方計算的安全性定義來形式化描述，即理想現(xiàn)實模擬范式(idealreal simulation paradigm).在這樣一種范式中，存在理想世界(ideal eorld)和現(xiàn)實世界(real world)兩種場景.在理想世界中，有一個完全可信的第三方，其接收參與方的輸入并計算某些功能函數(shù)(functionality)，然后將相關輸出信息返回給參與方；與此不同，在現(xiàn)實世界中，參與方不借助可信第三方的幫助，他們之間通過交互式地運行某些協(xié)議來得到相應的輸出結果.一個現(xiàn)實世界中的協(xié)議如果說是安全的，當且僅當沒有敵手能在現(xiàn)實世界中作出比理想世界更多的惡意行為.這可以表示為，對任意在現(xiàn)實世界中執(zhí)行了一個成功攻擊的敵手，總存在一個理想世界的敵手也能夠成功執(zhí)行相同的攻擊.為了形式化定義上述安全性，我們比較一個敵手在現(xiàn)實世界中與一個誠實參與方的聯(lián)合輸出分布(joint output distribution)，以及在有可信第三方存在的理想世界中的聯(lián)合輸出分布.如果以上2種世界中的聯(lián)合輸出分布是計算不可區(qū)分的，則說明該協(xié)議是安全的.根據(jù)不同的安全性需求，文獻[2]針對OT協(xié)議給出了3種安全性定義，即只保證隱私性(privacy only)、單邊模擬(one-sided simulation)以及完全模擬(full simulation)，其中完全模擬較之于前兩者安全性更高，設計能實現(xiàn)完全模擬的OT協(xié)議也更困難.

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為素數(shù).我們說群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是生成元，且存在一個證據(jù)w滿足h0=(g0)w,h1=(g1)w.

上述單一DH元組知識的零知識證明協(xié)議，在文獻[2-3]中已經(jīng)給出，在我們的協(xié)議中用到的是對該協(xié)議的一個擴展，即證明多個元組均為DH元組，且對應的證據(jù)w相同.具體地，我們要證明如下關系：

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

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

我們可以證明(g0,h0,g1,h1),(g0,h0,g2,h2),…,(g0,h0,gn,hn)都是DH元組，且每個DH元組的證據(jù)相同.然而，注意到以上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元組，即存在一個證據(jù)w滿足h0=(g0)w,h′=(g′)w，則必然要滿足h1=(g1)w,h2=(g2)w,…,hn=(gn)w.具體協(xié)議描述如下:

協(xié)議1. 批量DH元組的知識的零知識證明協(xié)議.

公共輸入：證明者P和驗證者V共同擁有輸入R={(G,q,(g0,h0),(g1,h1),…,(gn,hn))}，其中群G的階為素數(shù)q，生成元為g0，其他為群G中的元素；

證明者P的輔助輸入：P擁有一個證據(jù)w滿足h0=(g0)w,h1=(g1)w,…,hn=(gn)w.

協(xié)議：

步驟1.P隨機選擇值a∈{1,2,…,q}，并計算α=(g0)a，然后將α發(fā)送給V.

步驟2.V隨機選擇值s,t，a1,a2,…,an∈{1,2,…,q}，并計算c=(g0)s×αt和g′=(g1)a1×(g2)a2×…×(gn)an，然后將c和g′發(fā)送給P(這是對c的完美隱藏承諾，且a1,a2,…,an是某隨機線性組合的系數(shù)).

步驟3.P隨機選擇值r∈{1,2,…,q}，并計算A=(g0)r和B=(g′)r，然后將(A,B)發(fā)送給V.

步驟4.V將s,t發(fā)送給P.

步驟5.P驗證是否c=(g0)s×αt，如果不成立則中止;否則，P計算z=s×w+r，然后將z和a(在步驟1中所選)發(fā)送給V.

步驟6.V驗證以下是否成立：

1)α=(g0)a；

上述協(xié)議需要5輪交互，參與者交換9個群元素(其中P發(fā)送5個，V發(fā)送4個).此外，參與者共計算2n+12次指數(shù)運算(其中P計算5個，V計算2n+7個).

2.3RAND函數(shù)

RAND函數(shù)是定義在群G上的一個映射函數(shù).給定一個q階群G，其生成元是g.定義函數(shù)RAND(w,x,y,z)=(u,v)，滿足u=(w)s×(y)t且v=(x)s×(z)t，其中s,t∈q.RAND函數(shù)有以下性質：

聲明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) 計算不可區(qū)分性.如果說2個分布總體X={X(a,n)}a∈{0,1}*;n∈和Y={Y(a,n)}a∈{0,1}*;n∈是計算不可區(qū)分的，表示為X≡Y.需要滿足當對每個非均勻多項式時間算法D總存在一個可忽略函數(shù)μ(·)，對于每個a∈{0,1}*和每個n∈，有:

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

2) 完全模擬的安全性定義.惡意敵手模型下兩方計算的安全性定義主要基于理想/現(xiàn)實模擬范例.文獻[2]給出了形式化定義如下：

定義1. 令f:{0,1}*×{0,1}*→{0,1}*×{0,1}*是一個兩方功能函數(shù)，π是一個真實的兩方協(xié)議.若協(xié)議π在惡意敵手模型下安全計算f，必須滿足針對現(xiàn)實模型中的每個非均勻概率多項式時間敵手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茫然傳輸協(xié)議

3.1n取1茫然傳輸協(xié)議

在本節(jié)中，我們給出一個標準惡意敵手模型下可以完全模擬的n取1茫然傳輸協(xié)議.協(xié)議的主要思想是讓接收方構造n個四元組，滿足僅有一個元組符合DH元組屬性.為了阻止參與方的惡意行為，我們引入知識的零知識證明技術.協(xié)議具體表述如下:

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

輔助輸入: 安全參數(shù)n，以及一個q階群G，其生成元為g0；

輸出:R輸出xσ.

協(xié)議：

步驟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))發(fā)送給S.

步驟2.R使用知識的零知識證明系統(tǒng)向S證明存在一個值α，滿足：

步驟3. 接收方R隨機選擇一個值r∈q，并計算g=(gσ)r,h=(hσ)r，然后將(g,h)發(fā)送給S.

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

① 定義函數(shù)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，發(fā)送方S計算(ui,vi)=RAND(gi,g,hi,h)，然后計算wi=vi×xi，并將(ui,wi)發(fā)送給R.

3.2 協(xié)議正確性分析

如果協(xié)議雙方都誠實按照協(xié)議執(zhí)行，可以保證R只得到xσ.我們分別針對i=σ以及i≠σ這2種情況分析上述協(xié)議的正確性.

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 協(xié)議形式化證明

直觀地說，因為接收方R要通過知識的零知識證明系統(tǒng)向發(fā)送方S證明其構造的四元組滿足要求，所以R只能得到參與方輸入的某一個值，因此除了這個值以外的其他輸入值對于R來說依然是保密的.考慮R的輸入隱私性，因為群上的DDH問題是困難的，所以接收方S不能判斷哪一個元組是DH元組，從而也就不知道R的選擇什么.以下我們將根據(jù)2.4節(jié)的安全性定義給出協(xié)議的形式化證明.

證明. 我們在混合模型下證明上述協(xié)議的安全性，其中知識的零知識證明被一個理想功能函數(shù)計算.證明分為S被腐化和R被腐化這2種情況.

1)S被腐化.令A為現(xiàn)實世界的敵手，其控制發(fā)送方S.我們構造一個模擬器SSEND調(diào)用敵手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))發(fā)送給A.

步驟2. SSEND模擬知識的零知識證明系統(tǒng)的理想功能函數(shù)，并把1輸送給敵手A，這意味著接收方R的零知識證明通過驗證.

步驟3. SSEND隨機選擇一個值r∈q并計算g=(gσ)r,h=(hσ)r，然后將(g,h)發(fā)送給A.

步驟4. 收到A發(fā)送的(u0,w0),(u1,w1),…,(un-1,wn-1)，模擬器SSEND像誠實的R一樣計算所有的值(x0,x1,…,xn-1);然后將這些值發(fā)送給計算茫然傳輸協(xié)議的功能函數(shù)，并輸出敵手A輸出的內(nèi)容，然后中止.

以上是S被腐化的理想模擬過程.我們要證明在理想世界中模擬器SSEND和一個誠實的接收方R執(zhí)行的聯(lián)合輸出分布，與敵手A和誠實的R在現(xiàn)實協(xié)議中產(chǎn)生的輸出聯(lián)合分布計算不可區(qū)分，即

注意到以上理想模擬過程與現(xiàn)實協(xié)議的唯一不同是協(xié)議步驟中(h0,h1,…,hn-1)的構造方式.在理想模擬中，模擬器SSEND錯誤構造(h0,h1,…,hn-1)，使得所有的元組(g0,g,h0,h),(g1,g,h1,h),…,(gn-1,g,hn-1,h)都是DH元組.但是在現(xiàn)實協(xié)議中，只有唯一的1個元組(gσ,g,hσ,h)是DH元組，而其他元組均是非DH元組.假設以上2個輸出聯(lián)合分布能以不可區(qū)分的概率被區(qū)分開來，則一定存在一個區(qū)分器D以相同的概率區(qū)分一個DH元組和一個非DH元組，然而這與群上的DDH問題是困難的相矛盾，因此上述IDEAL分布和HYBRID分布是計算不可區(qū)分的.

2)R被腐化. 令A為現(xiàn)實世界的敵手，其控制接收方R.我們構造一個模擬器SREC調(diào)用敵手A的輸入，并作如下操作：

步驟1. 模擬器SREC從敵手A處接收到值(h0,(g1,h1),…,(gn-1,hn-1),(g,h))，并像誠實的發(fā)送方S一樣驗證零知識證明.

① 如果驗證失敗，SREC發(fā)送⊥至計算茫然傳輸功能函數(shù)的可信第三方，并中止協(xié)議.

② 否則，SREC運行零知識證明的抽取器，抽取出證據(jù)α.然后，對于i=0,1,…,n-1，SREC計算(g)α+i并與h比較，將與h相等的值i設置為敵手A的真實輸入σ.

步驟2. SREC將敵手A的真實輸入σ發(fā)送給計算茫然傳輸功能函數(shù)的可信第三方，并得到值xσ.

步驟3. SREC使用步驟2中得到的值xσ，像一個誠實發(fā)送方S一樣正確計算(uσ,wσ).而對于那些索引i≠σ，SREC設置(ui,wi)為群G中的任意元素.最后SREC將這些值(u0,w0),(u1,w1),…,(un-1,wn-1)發(fā)送給敵手A，輸出敵手A輸出的內(nèi)容，并中止協(xié)議.

以上是R被腐化的理想模擬過程.注意到在上述協(xié)議中，發(fā)送方S并沒有輸出，因此我們只需要證明在理想世界中敵手A和模擬器SREC執(zhí)行的輸出分布，與敵手A和誠實的S在現(xiàn)實協(xié)議中產(chǎn)生的輸出分布是計算不可區(qū)分的，即

通過比較IDEAL和HYBRID的執(zhí)行過程，唯一的不同就是對于那些索引i≠σ，值(ui,wi)的生成方式.在理想模擬中，這些值是模擬器SREC從群G中隨機選取的群元素；而在現(xiàn)實協(xié)議中，這些值是由誠實的發(fā)送方S使用RAND函數(shù)計算而得的.因為對于任意i≠σ，元組(gi,g,hi,h)都不是DH元組.根據(jù)RAND函數(shù)的性質，使用非DH元組計算所得的值在群G中是獨立隨機的，因此在理想模擬和現(xiàn)實協(xié)議中這些值是計算不可區(qū)分的.鑒于此，我們推出上述理想模擬和現(xiàn)實協(xié)議的輸出分布是不可區(qū)分的.

綜上所述，我們完成對定理1的證明.

證畢.

3.4 協(xié)議效率分析與比較

我們主要從3個方面針對上述協(xié)議的效率作出分析：

1) 交互輪數(shù). 上述協(xié)議共需要6輪交互，其中包括零知識證明的交互輪數(shù).

2) 本地指數(shù)計算量. 除去零知識證明協(xié)議中的計算量，在上述協(xié)議中發(fā)送方S和接收方R分別計算4n和2n+2次指數(shù)操作.加上零知識證明子協(xié)議中的2(n-1)+12次，協(xié)議的總指數(shù)計算量是8n+12.

3) 帶寬. 除去零知識證明協(xié)議中參與方的通信量，在上述協(xié)議中發(fā)送方S和接收方R分別發(fā)送2n和2n+1個群元素.加上零知識證明協(xié)議中共發(fā)送的9個群元素，協(xié)議的總帶寬為4n+10.

表1是我們的協(xié)議與已有的部分n取1茫然傳輸協(xié)議的對比結果.其中,文獻[12-14]中的協(xié)議不能在標準惡意敵手模型下被全模擬，而我們的協(xié)議可以實現(xiàn)全模擬，所達到的安全性更強；方案[16,18]中的協(xié)議雖然能達到UC安全這樣一種更強的安全性，但是其協(xié)議需要公共參考串的存在，且方案[18]中的協(xié)議復雜度為O(nlogn)，而我們的協(xié)議是在標準模型下安全的，不需要公共參考串的存在，且復雜度僅與n線性先關.

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

4 結束語

2) 在更為復雜的安全模型下，如UC模型、自適應模型等，設計更為高效的茫然傳輸協(xié)議.

[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)

(曲亞東, 侯紫峰, 韋衛(wèi). 基于不經(jīng)意傳輸?shù)暮贤炗唴f(xié)議[J]. 計算機研究與發(fā)展, 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)

(張斌, 徐秋亮, 蔣瀚. 新的可抵抗自適應敵手的可組合茫然傳輸協(xié)議[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).