趙圣楠 蔣 瀚 魏曉超 柯俊明 趙明昊

1(山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 濟(jì)南 250101) 2(山東師范大學(xué)信息科學(xué)與工程學(xué)院 濟(jì)南 250358) (yucheng＿zhao@163．com)

2017-06-11；

2017-07-29

國家自然科學(xué)基金項(xiàng)目(61572294)；國家自然科學(xué)基金青年科學(xué)基金項(xiàng)目(61602287)；國家自然科學(xué)基金重點(diǎn)項(xiàng)目(61632020)；山東大學(xué)基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(2017JC019) This work was supported by the National Natural Science Foundation of China (61572294), the National Natural Science Foundation of China for Young Scientists (61602287), the Key Program of the National Natural Science Foundation of China (61632020), and the Fundamental Research Funds of Shandong University (2017JC019).

蔣瀚(jianghan@sdu.edu.cn)

一個(gè)單服務(wù)器輔助的高效n取k茫然傳輸協(xié)議

趙圣楠1蔣 瀚1魏曉超2柯俊明1趙明昊1

1(山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 濟(jì)南 250101)2(山東師范大學(xué)信息科學(xué)與工程學(xué)院 濟(jì)南 250358) (yucheng＿zhao@163．com)

茫然傳輸；外包計(jì)算；判定性Diffie-Hellamn假設(shè)；半誠實(shí)模型；安全多方計(jì)算

外包計(jì)算作為當(dāng)今新型的計(jì)算模式，日漸受到研究者和企業(yè)界的關(guān)注.物聯(lián)網(wǎng)、移動(dòng)計(jì)算、無線傳感器網(wǎng)絡(luò)等技術(shù)的興起和普及極大地方便了我們的生活、溝通與信息獲取，但是出于效率和成本等因素的考慮，這類設(shè)備通常采用輕量級(jí)硬件架構(gòu)，計(jì)算和存儲(chǔ)能力受到極大的限制.

云計(jì)算的興起為能力受限的移動(dòng)設(shè)備提供了完美的后端支持.當(dāng)前的服務(wù)計(jì)算架構(gòu)中，一方面云服務(wù)器為移動(dòng)設(shè)備提供視頻分發(fā)、數(shù)據(jù)分析以及廣告推送等服務(wù)；另一方面移動(dòng)設(shè)備會(huì)將復(fù)雜的計(jì)算任務(wù)外包到云端，云端完成計(jì)算任務(wù)后將計(jì)算結(jié)果返回給移動(dòng)設(shè)備.云計(jì)算和外包計(jì)算模式，極大地豐富了移動(dòng)計(jì)算的內(nèi)容[1].

出于安全和隱私性考慮，移動(dòng)設(shè)備(如手機(jī)客戶端、RFID芯片、傳感器網(wǎng)絡(luò)節(jié)點(diǎn)等)之間往往需要執(zhí)行認(rèn)證和加密等多種密碼學(xué)原語，其中以公鑰密碼原語居多.在公鑰密碼中通常需要涉及大量的群上的指數(shù)運(yùn)算，這對(duì)于移動(dòng)設(shè)備來說是極大的負(fù)擔(dān).目前雖然可以設(shè)計(jì)專用的嵌入式芯片來高速實(shí)現(xiàn)密碼原語操作[2-3]，但這一定程度上會(huì)增加設(shè)備成本.因此，目前一個(gè)很理想的解決方案是將公鑰加密方案的部分復(fù)雜運(yùn)算外包到云端來進(jìn)行.

茫然傳輸(oblivious transfer, OT)是密碼學(xué)中一個(gè)基礎(chǔ)工具.傳統(tǒng)的茫然傳輸協(xié)議中有2個(gè)參與方：發(fā)送方S和接收方R，協(xié)議的目的是讓接收方從發(fā)送方的輸入中獲取自己選擇的輸入，且滿足：1)發(fā)送方不知道接收方的選擇；2)接收方只能獲得自己選擇的輸入且無法獲得額外的輸入信息.茫然傳輸在隱私保護(hù)的數(shù)據(jù)查詢、安全多方計(jì)算等多個(gè)領(lǐng)域有重要應(yīng)用[4].

1 相關(guān)工作和主要結(jié)論

1.1相關(guān)工作

雙向OT使得每個(gè)參與方都兼有發(fā)送者和接受者的雙重身份，該原語可以大大降低基于cut-and-choose的安全多方計(jì)算協(xié)議的輪復(fù)雜度.Zhao等人[27]和Wei等人[28]在雙向OT領(lǐng)域做出了創(chuàng)舉性的研究；抗量子OT有文獻(xiàn)[29-30]等.

密碼學(xué)原語的部分外包.通常來講群指數(shù)運(yùn)算是密碼算法中最為耗時(shí)的運(yùn)算.Dijk等人[31]首先考慮將指數(shù)運(yùn)算外包給一個(gè)不可信的服務(wù)器；Ma等人[32]考慮了將指數(shù)操作外包到2個(gè)非合謀的不可信服務(wù)器；Hohenberger等人[33]和Chen等人[34]將變基和變冪的指數(shù)算法外包到(雙服務(wù)器模型下的)單一惡意服務(wù)器，即要求2個(gè)服務(wù)器中僅有一個(gè)服務(wù)器為惡意的，且不與另一個(gè)誠實(shí)服務(wù)器合謀.文獻(xiàn)[34]同時(shí)考慮了安全與高效的并發(fā)指數(shù)(simultaneous exponentiations)操作外包；Wang等人[35]實(shí)現(xiàn)了一個(gè)單一非可信服務(wù)器模型下的指數(shù)運(yùn)算外包方案；Chevalier等人[36]對(duì)該方案做了細(xì)致的密碼學(xué)分析，并給出了一個(gè)優(yōu)化的構(gòu)造方案；Tsang等人[37]首先考慮了以批量的方式將橢圓曲線上的點(diǎn)對(duì)運(yùn)算(pairing)外包到云服務(wù)器上來實(shí)現(xiàn)；Canard等人[38]給出了一個(gè)更為高效的安全點(diǎn)對(duì)運(yùn)算外包方案；Xu等人[39]考慮將復(fù)雜運(yùn)算外包到計(jì)算服務(wù)器P，并將外包計(jì)算結(jié)果的正確性驗(yàn)證外包到驗(yàn)證服務(wù)器V，其隱私性保證不向計(jì)算服務(wù)器和驗(yàn)證服務(wù)器泄漏數(shù)據(jù)信息；Gennaro等人[40]首次提出非交互的可驗(yàn)證外包計(jì)算；Carter等人[41]將基于cut-and-choose安全多方計(jì)算中的混亂電路求值外包給云服務(wù)器來做；文獻(xiàn)[42-43]則將混亂電路的生產(chǎn)任務(wù)外包給移動(dòng)設(shè)備；服務(wù)器輔助的通用兩方計(jì)算協(xié)議方案有文獻(xiàn)[44-45]等.和本文工作最為相關(guān)的是Wei等人[45]提出的云服務(wù)器輔助茫然傳輸協(xié)議，該方案涉及2個(gè)非合謀的服務(wù)器且在半誠實(shí)模型下達(dá)到可證明安全.

1.2本文工作

我們?cè)O(shè)計(jì)了一種新的基于單個(gè)云服務(wù)器的k-out-of-nOT協(xié)議.文獻(xiàn)[45]將群指數(shù)運(yùn)算外包到2個(gè)誠實(shí)但好奇且相互獨(dú)立的云服務(wù)器上，云服務(wù)器誠實(shí)但好奇的性質(zhì)說明該協(xié)議是在半誠實(shí)模型下執(zhí)行，云服務(wù)器之間相互獨(dú)立意味著2個(gè)云服務(wù)器之間不能合謀.該方案雖然降低了通信雙方的本地計(jì)算量，卻存在2個(gè)明顯的弊端：首先外包計(jì)算目前仍需要支付大量的費(fèi)用，將群指數(shù)運(yùn)算外包到2個(gè)云服務(wù)器更是要有足夠的經(jīng)濟(jì)支撐，出于預(yù)算考慮在某些應(yīng)用場(chǎng)景下不得不放棄使用該協(xié)議；再者，2個(gè)云服務(wù)器不能合謀的安全假設(shè)過于理想，2個(gè)云服務(wù)器一旦合謀就可以知道接收方的輸入選擇，或者云服務(wù)器與接收方合謀來獲得發(fā)送方的全部輸入，這樣協(xié)議的安全性就完全得不到保證.因此，我們希望在保證安全和效率的基礎(chǔ)上將云服務(wù)器的個(gè)數(shù)減少至一個(gè)，從而避免2個(gè)云服務(wù)器合謀的嚴(yán)重弊端.我們具體的貢獻(xiàn)有3方面：

1) 將RAND 函數(shù)的計(jì)算過程分散到發(fā)送方和云服務(wù)器，并以一種新的形式嵌入發(fā)送方的輸入值.

2) 將群指數(shù)運(yùn)算外包到一個(gè)云服務(wù)器，設(shè)計(jì)出基于單個(gè)云輔助的高效n取k茫然傳輸協(xié)議，該協(xié)議是安全三方計(jì)算的實(shí)例，并依據(jù)誠實(shí)方大多數(shù)原則證明其安全性.

3) 相對(duì)于其他基于DDH假設(shè)的n取k茫然傳輸協(xié)議，我們將協(xié)議的計(jì)算和通信復(fù)雜度降至O(n)量級(jí).

2 基本知識(shí)和安全定義

2.1DH元組

令G為一個(gè)以g為生成元的q階群，q為素?cái)?shù).將形如(gα,gβ,gαβ)的三元組稱為DH元組，這里的α,β隨機(jī)取自q.也就是說，對(duì)于任意群G上的三元組(gα,gβ,gγ)，α,β,γ∈q，若γ≡α×β(modq)則稱該元組為DH元組，否則為非DH元組.

2.2DDH假設(shè)

DDH問題定義：給定上述群G上的四元組(g,gα,gβ,gγ)，α,β,γ∈q，判定γ≡α×β(modq)是否成立.若等式成立，由于該元組的第1個(gè)元素為生成元，所以該四元組與上述所定義的三元組構(gòu)成的DH元組并不矛盾，四元組(g,gα,gβ,gγ)仍稱為DH元組.將生成元看作一個(gè)公開參數(shù)，那么任意三元組都可以寫成四元組的形式，因此從現(xiàn)在起所有的DH元組均默認(rèn)為四元組.那么，DDH假設(shè)是指下述2種總體分布是計(jì)算不可區(qū)分的：

1)X1=(g,ga,gb,ga b)，這里a,b∈q；

2)X2=(g,ga,gb,gc)，這里a,b∈q，但ab≠c.

2.3RAND函數(shù)

RAND函數(shù)定義在群G構(gòu)成的DH元組(w,x,y,z)上，w,x,y,z∈G，函數(shù)RAND(w,x,y,z)=(u,v)，其中u=ws×yt，v=xs×zt，這里s,t∈q.注意，對(duì)任意的DH元組(w,x,y,z)，必然存在a∈q，滿足y=wa,z=xa.因此，RAND函數(shù)有性質(zhì)：

1) 如果(w,x,y,z)是DH元組且滿足y=wa，z=xa，那么對(duì)于u,v←RAND(w,x,y,z)滿足ua=v.

2) 如果(w,x,y,z)為非DH元組，那么(w,x,y,z,RAND(w,x,y,z))，(w,x,y,z,ga,gb)在分布上是等價(jià)的，這里α,β隨機(jī)取自q.

顯然，RAND函數(shù)的計(jì)算過程能夠分為ws，yt，xs和zt這4個(gè)部分，我們可以將這4個(gè)部分分發(fā)給不同參與方，然后聯(lián)合計(jì)算出函數(shù)值.

2.4安全性定義

本文中我們考慮基于單服務(wù)器輔助的n取k茫然傳輸協(xié)議.為了定義基于云服務(wù)器外包協(xié)議的安全性，我們參考了文獻(xiàn)[45-46]中提出的安全多方計(jì)算在外包環(huán)境中安全定義.在文獻(xiàn)[45]中協(xié)議是基于2個(gè)相互獨(dú)立的云服務(wù)器，我們的協(xié)議將云服務(wù)器個(gè)數(shù)減少為一個(gè)，相當(dāng)于發(fā)送方在協(xié)議執(zhí)行過程中扮演了原方案中一個(gè)云服務(wù)器的角色.協(xié)議共涉及3個(gè)參與方，因此我們將協(xié)議的執(zhí)行過程看作是安全三方計(jì)算的實(shí)例，遵循誠安全多方計(jì)算里誠實(shí)方大多數(shù)原則，即在該協(xié)議中敵手只能腐化至多一個(gè)參與方，因此不考慮任意2方合謀的情況.我們?cè)O(shè)計(jì)的協(xié)議中，仍然定義云服務(wù)器是誠實(shí)但好奇的，且與協(xié)議雙方保持獨(dú)立.誠實(shí)但好奇意味著云服務(wù)器不僅根據(jù)指令誠實(shí)地執(zhí)行協(xié)議的每一步操作，并且想要依據(jù)接收到的消息副本來試圖獲得發(fā)送方或接收方的輸入.但云服務(wù)器不能與發(fā)送方或接收方中的任意一方合謀，也就是說云服務(wù)器只負(fù)責(zé)提供額外的計(jì)算能力或者依照協(xié)議指令傳送特定內(nèi)容.

現(xiàn)在我們分別定義發(fā)送方安全和接收方安全.

3) 針對(duì)接收方的發(fā)送方安全定義.對(duì)于接收方的任意選擇集合C={σ1,σ2,…,σk}，發(fā)送方對(duì)接收方并未選擇地輸入值的加密結(jié)果應(yīng)與隨機(jī)計(jì)算不可區(qū)分.

3 單服務(wù)器輔助的n取k茫然傳輸協(xié)議

在本節(jié)中，我們給出一個(gè)半誠實(shí)敵手模型下的單服務(wù)器輔助的n取k茫然傳輸協(xié)議的具體過程.

協(xié)議所設(shè)計(jì)的系統(tǒng)模型如圖1所示.協(xié)議共涉及3個(gè)參與方:發(fā)送方S、接收方R和云服務(wù)器Server.協(xié)議一共需要進(jìn)行3輪交互.首先，R根據(jù)自己的選擇構(gòu)造出多項(xiàng)式，并將多項(xiàng)式的系數(shù)分割成2部分分別發(fā)送給S和Server；接著，S接收到的部分系數(shù)后計(jì)算RAND函數(shù)的部分結(jié)果，并將自己的輸入嵌入到其中；最后，Server接收到來自S和R的消息后完成RAND函數(shù)的全部運(yùn)算，將函數(shù)值發(fā)送給R，R在本地進(jìn)行解密獲得自己所選的值.

Fig. 1 The system model圖1 系統(tǒng)模型

協(xié)議.單服務(wù)器輔助的高效n取k茫然傳輸協(xié)議.

輸入：S輸入n個(gè)值(x1,x2,…,xn)∈{0,1}n、R輸入k個(gè)值(σ1,σ2,…,σk)∈{1,2,…,n}、云服務(wù)器Server沒有輸入；

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

協(xié)議執(zhí)行過程：

步驟1.R隨機(jī)選擇一個(gè)k階多項(xiàng)式f(x)=(x-σ1)(x-σ2)…(x-σk)+β=a0+a1x+…+ak-1xk-1+xkmodq，其中β∈q.針對(duì)任意i=0,1,…,k-1，R計(jì)算并將(c0,c1)發(fā)送給S，將(c2,c3,…,ck-1)發(fā)送給云服務(wù)器Server.然后，R隨機(jī)選擇y1,y2,…,yn∈q，并將這n個(gè)值分別發(fā)送給S和Server.此外，R隨機(jī)選擇一個(gè)σm∈{σ1,σ2,…,σk}以及r∈q，并計(jì)算和h=gβ，然后將(g,h)發(fā)送給Server.

步驟4.R輸出：

1) 針對(duì)步驟1中R隨機(jī)選擇的σm，R計(jì)算：

2) 針對(duì)每一個(gè)σj∈{σ1,σ2,…,σk}且σj?σm，R計(jì)算：

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

1) 針對(duì)i=σm，有f(i)=β，

2) 針對(duì)每一個(gè)i∈{σ1,σ2,…,σk}但i≠σm,同樣有f(i)=β，計(jì)算得到：

3) 當(dāng)i∈{1,2,…,n}但i?{σ1,σ2,…,σk}，此時(shí)f(i)≠β，則計(jì)算為

綜上可以看出，接收方R能且僅能獲得與自己選擇相對(duì)應(yīng)的k個(gè)值.

3.3協(xié)議安全性證明

下面我們給出協(xié)議的形式化安全證明.

定理1. 如果云服務(wù)器Server是誠實(shí)但好奇的且與發(fā)送方S相互獨(dú)立，那么針對(duì)發(fā)送方協(xié)議滿足接收方的安全性要求.

證畢.

定理2. 如果在群G上DDH假設(shè)成立，并且發(fā)送方S與云服務(wù)器Server是誠實(shí)但好奇的且相互獨(dú)立，那么針對(duì)云服務(wù)器協(xié)議滿足接收方的安全性要求.

證畢.

定理3. 如果在群G上DDH假設(shè)成立，并且發(fā)送方S與云服務(wù)器Server是誠實(shí)但好奇的且相互獨(dú)立，那么針對(duì)接收方協(xié)議滿足發(fā)送方的安全性要求.

證明. 首先我們分析接收方R通過惡意行為來獲取除自己選擇外的值.接收方R可以試圖構(gòu)造一個(gè)多項(xiàng)式f(x)滿足f(1)=f(2)=…=f(n)=β，從而可以恢復(fù)出發(fā)送方S的n個(gè)輸入.這必然導(dǎo)致所構(gòu)造出的多項(xiàng)式的階大于k，在協(xié)議中云服務(wù)器Server檢查了接收方R所發(fā)送的系數(shù)的個(gè)數(shù)，利用這個(gè)方法可以將多項(xiàng)式f(x)的階嚴(yán)格限制為k，因此n個(gè)元組中DH元組的個(gè)數(shù)也是k.接下來證明接收方R不可能從n-k個(gè)非DH元組中獲取額外信息.

根據(jù)RAND函數(shù)的性質(zhì)，如果(w,x,y,z)為非DH元組，那么RAND(w,x,y,z)的結(jié)果是群G中的隨機(jī)值.假設(shè)接收方的輸入為(σ1,σ2,…,σk)，對(duì)于每一個(gè)j?{σ1,σ2,…,σk}對(duì)應(yīng)的(gj,g,hj,h)都不是DH元組.不妨從q中隨機(jī)選擇a和b，使得hj=(gj)a，h=gb,且a≠b.為了證明RAND(gj,g,hj,h)的結(jié)果在群G中是隨機(jī)的，只需說明這里α,β隨機(jī)取自q.由于RAND(gj,g,hj,h)=((gj)s×(hj)t,(g)s×(h)t)，這里s,t隨機(jī)取自q，因此上述的概率是來自于s和t的隨機(jī)性.令g=(gj)γ，γ隨機(jī)取自q，那么元組(gj,g,hj,h)可以表示為(gj,(gj)γ,(gj)a,(gj)γ×b)，相應(yīng)的RAND(gj,g,hj,h)=((gj)s+a×t,(gj)s×γ+γ×b×t).這樣，對(duì)于方程組：

綜上所述，我們完成對(duì)協(xié)議的安全性證明.

證畢.

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

我們?cè)O(shè)計(jì)的協(xié)議中需要交互3輪:第1輪接收方R向同時(shí)向發(fā)送方S和云服務(wù)器Server發(fā)送消息；第2輪發(fā)送方S向云服務(wù)器Server發(fā)送一系列本地計(jì)算的結(jié)果；第3輪云服務(wù)器Server接收到發(fā)送方S發(fā)送的消息后將四元組“加密”后發(fā)送給接收方R，R在本地進(jìn)行解密運(yùn)算.

每一輪中具體的指數(shù)運(yùn)算如下：

2) 發(fā)送方S共進(jìn)行了4n-1次群指數(shù)運(yùn)算.2n次群指數(shù)運(yùn)算用來計(jì)算矩陣：

n-1次群指數(shù)運(yùn)算用來計(jì)算矩陣：

3) 云服務(wù)器Server共進(jìn)行2(k+1)n+1-k次群指數(shù)運(yùn)算.(k-1)n次用于計(jì)算矩陣：

(n-1)(k-1)次用于計(jì)算矩陣：

最后，我們統(tǒng)計(jì)出協(xié)議中的各參與方發(fā)送的群元素的個(gè)數(shù)：

3) 云服務(wù)器Sever把2n個(gè)元素發(fā)送給接收方R：(u1,w1),(u2,w2),…,(un,wn).

表1是我們所設(shè)計(jì)的協(xié)議與文獻(xiàn)[12,45]的對(duì)比結(jié)果.Chu等人[19]提出的n取k茫然傳輸協(xié)議不需要云服務(wù)器輔助，因此需要發(fā)送方和接收方進(jìn)行大量群指數(shù)運(yùn)算.Wei等人提出的協(xié)議將大部分群指數(shù)運(yùn)算外包至2個(gè)云服務(wù)器，從而降低發(fā)送方和接收方的群指數(shù)運(yùn)算.我們的協(xié)議僅使用一個(gè)云服務(wù)器且相對(duì)高效.

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

4 結(jié)束語

[1] Li Zhenhua, Dai Yafei, Chen Guihai, et al. Content Distribution for Mobile Internet: A Cloud-based Approach[M]. Singapore: Springer Science Business Media, 2016

[2] Liu Zhe, Weng Jian, Hu Zhi, et al. Efficient elliptic curve cryptography for embedded devices[J]. ACM Trans on Embedded Computing Systems, 2016, 16(2): Article No 53

[3] Liu Zhe, Seo H, Gro?sch?dl J, et al. Efficient imple-mentation of NIST-compliant elliptic curve cryptography for 8-bit AVR-based sensor nodes[J]. IEEE Trans on Information Forensics and Security, 2016, 11(7): 1385-1397

[4] Jiang Han, Xu Qiuliang. Advances in key techniques of practical secure multi-party computation[J]. Journal of Computer Research and Development, 2015, 52(10): 2247-2257 (in Chinese)

(蔣瀚, 徐秋亮. 實(shí)用安全多方計(jì)算協(xié)議關(guān)鍵技術(shù)研究進(jìn)展[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(10): 2247-2257)

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

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

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

[8] 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

[9] Cramer R, Shoup V. Universal Hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption[G] //LNCS 2332: Advances in Cryptology (EUROCRYPT 2002). Berlin: Springer, 2002: 45-64

[10] Kalai Y T. Smooth projective hashing and two-message oblivious transfer[G] //LNCS 3494: Advances in Cryptology (EUROCRYPT 2005). Berlin: Springer, 2005: 78-95

[11] 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.

[12] Tzeng W G. Efficient 1-out-noblivious transfer schemes[G] //LNCS 2274: Public Key Cryptography. Berlin: Springer, 2002: 159-171

[13] Wei Xiaochao, Jiang Han, Zhao Chuan. An efficient 1-out-of-noblivious transfer protocol with full simulation[J]. Journal of Computer Research and Development, 2016, 53(11): 2475-2481 (in Chinese)

(魏曉超, 蔣瀚, 趙川. 一個(gè)高效可完全模擬的n取1茫然傳輸協(xié)議[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(11): 2475-2481)

[14] Lindell A Y. Efficient fully-simulatable oblivious transfer[G] //LNCS 4964: Topics in Cryptology (CT-RSA 2008). Berlin: Springer, 2008: 52-70

[15] 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

[16] Feng Tao, Ma Jianfeng, Li Fenghua. Efficient and universally composable security oblivious transfer[J]. Acta Electronica Sinica, 2008, 36(1): 17-23 (in Chinese)

(馮濤, 馬建峰, 李鳳華. UC安全的高效不經(jīng)意傳輸協(xié)議[J]. 電子學(xué)報(bào), 2008, 36(1): 17-23)

[17] Green M, Hohenberger S. Universally composable adaptive oblivious transfer[G] //LNCS 5350: Advances in Cryptolog (Asiacrypt 2008). Berlin: Springer, 2008: 179-197

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

[19] Chu C K, Tzeng W G. Efficientk-out-of-noblivious transfer schemes with adaptive and non-adaptive queries[G] //LNCS 3386: Public Key Cryptography (PKC 2005). Berlin: Springer, 2005: 172-183

[20] Zhang Jianhong, Wang Yumin. Two provably securek-out-of-noblivious transfer schemes[J]. Applied Mathematics and Computation, 2005, 169(2): 1211-1220

[21] Camenisch J, Neven G, Shelat A. Simulatable adaptive oblivious transfer[G] //LNCS 4515: Advances in Cryptology (EUROCRYPT 2007). Berlin: Springer, 2007: 573-590

[22] Zeng Bin, Tartary C, Xu Peng, et al. A practical framework fort-out-of-noblivious transfer with security against covert adversaries[J]. IEEE Trans on Information Forensics and Security, 2012, 7(2): 465-479

[23] Harnik D, Ishai Y, Kushilevitz E, et al. OT-combiners via secure computation[G] //LNCS 4948: Theory of Cryptography. Berlin: Springer, 2008: 393-411

[24] Nielsen J B, Nordholt P S, Orlandi C, et al. A new approach to practical active-secure two-party computation[G]//LNCS 7417: Advances in Cryptology (CRYPTO 2012). Berlin: Springer, 2012: 681-700

[25] Asharov G, Lindell Y, Schneider T, et al. More efficient oblivious transfer extensions[J]. Journal of Cryptology, 2017, 30(3): 805-858

[26] Patra A, Sarkar P, Suresh A. Fast actively secure OT extension for short secrets[C] //Proc of the 24th Network and Distributed System Security Symp (NDSS). Reston, VA: Internet Society, 2017

[27] Zhao Chuan, Jiang Han, Wei Xiaochao, et al. Cut-and-choose bilateral oblivious transfer and its application[C] //Proc of the 14th IEEE Int Conf on Trust, Security and Privacy in Computing and Communications. Los Alamitos, CA: IEEE Computer Society, 2015: 384-391

[28] Wei Xiaochao, Jiang Han, Zhao Chuan, et al. Fast cut-and-choose bilateral oblivious transfer for malicious adversaries[C] //Proc of the 15th IEEE Int Conf on Trust, Security and Privacy in Computing and Communications. Los Alamitos, CA: IEEE Computer Society, 2016: 418-425

[29] Plesch M, Pawowski M, Pivoluska M. 1-out-of-2 oblivious transfer using a flawed bit-string quantum protocol[J]. Physical Review A, 2017, 95(4): 042324

[30] Yang Yugang, Yang Rui, Cao Weifeng, et al. Flexible quantum oblivious transfer[J]. International Journal of Theoretical Physics, 2017, 56(4): 1286-1297

[31] Van Dijk M, Clarke D, Gassend B, et al. Speeding up exponentiation using an untrusted computational resource[J]. Designs, Codes and Cryptography, 2006, 39(2): 253-273

[32] Ma Xu, Li Jin, Zhang Fangguo. Outsourcing computation of modular exponentiations in cloud computing[J]. Cluster Computing, 2013, 16(4): 787-796

[33] Hohenberger S, Lysyanskaya A. How to securely outsource cryptographic computations[G] //LNCS 3378: Theory of Cryptography Conference (TCC 2005). Berlin: Springer, 2005: 264-282

[34] Chen Xiaofeng, Li Jin, Ma Jianfeng, et al. New algorithms for secure outsourcing of modular exponentiations[J]. IEEE Trans on Parallel and Distributed Systems, 2014, 25(9): 2386-2396

[35] Wang Yujie, Wu Qianhong, Wong D S, et al. Securely outsourcing exponentiations with single untrusted program for cloud storage[G] //LNCS 8712: Computer Security (ESORICS 2014). Berlin: Springer, 2014: 326-343

[36] Chevalier C, Laguillaumie F, Vergnaud D. Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions[C] //LNCS 9878: Computer Security (ESORICS 2016). Berlin: Springer, 2016: 261-278

[37] Tsang P P, Chow S S M, Smith S W. Batch pairing delegation[G] //LNCS 4752: Advances in Information and Computer Security. Berlin: Springer, 2007: 74-90

[38] Canard S, Devigne J, Sanders O. Delegating a pairing can be both secure and efficient[G] //LNCS 8479: Applied Cryptography and Network Security. Berlin: Springer, 2014: 549-565

[39] Xu G, Amariucai G T, Guan Y. Delegation of computation with verification outsourcing: Curious verifiers[J]. IEEE Trans on Parallel and Distributed Systems, 2017, 28(3): 717-730

[40] Gennaro R, Gentry C, Parno B. Non-interactive verifiable computing: Outsourcing computation to untrusted workers[G] //LNCS 6223: Advances in Cryptology (CRYPTO 2010). Berlin: Springer, 2010: 465-482

[41] Carter H, Mood B, Traynor P, et al. Secure outsourced garbled circuit evaluation for mobile devices[J]. Journal of Computer Security, 2016, 24(2): 137-180

[42] Carter H, Lever C, Traynor P. Whitewash: Outsourcing garbled circuit generation for mobile devices[C] //Proc of the 30th Annual Computer Security Applications Conf. New York: ACM, 2014: 266-275

[43] Mohassel P, Orobets O, Riva B. Efficient server-aided 2PC for mobile phones[J]. Proceedings on Privacy Enhancing Technologies, 2016, 2016(2): 82-99

[44] Carter H, Mood B, Traynor P, et al. Outsourcing secure two-party computation as a black box[J]. Security and Communication Networks, 2016, 9(14): 2261-2275

[45] Wei Xiaochao, Zhao Chuan, Jiang Han, et al. Practical server-aidedk-out-of-noblivious transfer protocol[G] //LNCS 9663: Green, Pervasive, and Cloud Computing 2016. Berlin: Springer, 2016: 261-277

[46] Kamara S, Mohassel P, Raykova M. Outsourcing multi-party computation[OL]. [2017-08-25]. https://eprint.iacr.org/2011/272/pdf

AnEfficientSingleServer-Aidedk-out-of-nObliviousTransferProtocol

Zhao Shengnan1, Jiang Han1, Wei Xiaochao2, Ke Junming1, and Zhao Minghao1

1(SchoolofComputerScienceandTechnology,ShandongUniversity,Jinan250101)2(SchoolofInformationScienceandEngineering,ShandongNormalUniversity,Jinan250358)

oblivious transfer (OT); outsourcing computing; decisional Diffie-Hellamn (DDH) assumption; semi-honest model; secure multi-party computation

TP301

ZhaoShengnan, born in 1994. PhD candidate. His main research interests include secure multiparty computation and search on encrypted data.

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

WeiXiaochao, born in 1990. PhD and lecturer. His main research interests include secure multiparty computation and search on encrypted data (weixiaochao2008@163.com).

KeJunming, born in 1994. Master candidate. His main research interests include computer security and cryptocurrencies (Junmingke1994@gmail.com).

ZhaoMinghao, born in 1991. PhD candidate in Tsinghua University. Received his MSc degree in Shandong University and bachelor degree in Harbin Engineering University. Student member of ACM, CCF and CACR. His main research interests include cloud computing, storage system, mobile computing, privacy-preserving techniques and applied cryptography.