可證明安全的理性委托計(jì)算協(xié)議

田有亮，李秋賢，張鐸,3，王琳杰

（1. 貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025；2. 貴州省公共大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽 550025；3. 貴州大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，貴州 貴陽 550025）

1 引言

委托計(jì)算[1]是指計(jì)算能力相對(duì)較弱或資源受限的委托方將函數(shù)F的計(jì)算任務(wù)委托給不信任的計(jì)算方，計(jì)算方將返回一個(gè)計(jì)算結(jié)果及計(jì)算結(jié)果的正確性證明給委托方。委托方通過執(zhí)行驗(yàn)證協(xié)議來驗(yàn)證返回結(jié)果的正確性，并且委托方驗(yàn)證該證明的工作量比計(jì)算函數(shù)F的開銷要小得多，否則將失去委托計(jì)算的意義。委托計(jì)算一直受到學(xué)者的廣泛研究，主要有基于復(fù)雜性理論構(gòu)造方案和基于密碼技術(shù)構(gòu)造方案。基于復(fù)雜性理論構(gòu)造方案主要應(yīng)用的工具是交互式證明系統(tǒng)[2]、PCP（probabilistic checking of proofs）定理[3]等，Chung 等[4]在隨機(jī)語言模型下對(duì)非交互式委托計(jì)算進(jìn)行研究，給出了有效的解決方法?；诿艽a技術(shù)構(gòu)造方案主要應(yīng)用的工具有全同態(tài)加密[5]、基于屬性加密[6]、混淆電路[7]等，Gennaro等[8]利用文獻(xiàn)[7]的混淆電路構(gòu)造了非交互式的委托計(jì)算方案，該方案有效地解決了基于計(jì)算理論方案的困難性問題。

理性委托計(jì)算屬于理性密碼學(xué)的研究范圍，針對(duì)理性密碼協(xié)議的研究領(lǐng)域，大多學(xué)者較多地關(guān)注利用博弈論方法來解決秘密共享、安全多方計(jì)算等問題，涉及理性委托計(jì)算的研究尚少。理性委托計(jì)算結(jié)合博弈論與委托計(jì)算的思想，協(xié)議中參與者都是理性的，而不是誠實(shí)的或是惡意的，且協(xié)議中通過效用函數(shù)來保證計(jì)算結(jié)果的正確性。傳統(tǒng)的委托計(jì)算協(xié)議中，通常假設(shè)參與者要么是誠實(shí)的，要么是惡意的，但實(shí)際應(yīng)用中，參與者大多是理性的，因此理性委托計(jì)算的研究成為當(dāng)前的研究熱點(diǎn)。Azar等[9]根據(jù)適當(dāng)?shù)脑u(píng)分規(guī)則，提出了一種理性證明系統(tǒng)，該系統(tǒng)中參與者既不是誠實(shí)的，也不是惡意的，而是理性的；隨后Azar等[10]又利用Utility Gaps的思想構(gòu)造了一種超有效的理性證明系統(tǒng)；Guo等[11]通過對(duì)理性證明系統(tǒng)的研究，解決了證明者計(jì)算能力受限的理性證明系統(tǒng)問題；Tian等[12]從理性的角度分析了安全通信問題，并提出了貝葉斯理性秘密共享方案；隨后Chen等[13]從復(fù)雜性理論的角度研究了當(dāng)存在多個(gè)證明者時(shí)，理性證明系統(tǒng)的理性證明問題。

關(guān)于理性委托計(jì)算的安全性問題是研究者最為關(guān)心的，如何利用效用函數(shù)構(gòu)建安全可靠的理性委托計(jì)算協(xié)議更是當(dāng)前的研究需求。Kilian等[14]提出了證明者使用 Merkle樹向驗(yàn)證者發(fā)送對(duì)整個(gè)證明的短承諾的有效論證，證明者可以交互式地打開驗(yàn)證者的請(qǐng)求。Micali’s CS Proof[1]可以獲得非交互式解決方案，該解決方案根據(jù)隨機(jī)oracle應(yīng)用承諾字符串來選擇要打開的請(qǐng)求，消除涉及參數(shù)的交互。在最近的研究中，更多研究者較為關(guān)注非交互式協(xié)議，并且可以在標(biāo)準(zhǔn)模型中給予證明。

本文結(jié)合混淆電路和全同態(tài)加密技術(shù)提出了一種可證明安全的理性委托計(jì)算方案，該方案保證了所有理性參與者都得到最優(yōu)的利益，保證委托計(jì)算輸入和輸出的隱私性。本文的具體工作如下。

1) 通過分析參與者的行為策略及參與者選擇行為策略而得到的效用，設(shè)計(jì)了理性委托計(jì)算博弈模型。

2) 根據(jù)構(gòu)建的委托計(jì)算博弈模型中納什均衡需求，以及理性委托計(jì)算的安全需求，設(shè)計(jì)了可證明安全的理性委托計(jì)算安全模型。

3) 利用隨機(jī)化混淆電路可重用的優(yōu)點(diǎn)與全同態(tài)加密技術(shù)，保證了理性參與者結(jié)果的正確性及委托計(jì)算輸入和輸出隱私，從而構(gòu)建了安全的理性委托計(jì)算協(xié)議。

4) 對(duì)協(xié)議的安全性與性能進(jìn)行分析，證明了協(xié)議的安全性與輸入輸出隱私性，保證了所有參與者在協(xié)議中能獲得利益的最大化即達(dá)到唯一納什均衡。

2 基礎(chǔ)知識(shí)

2.1 博弈論

定義1博弈。博弈表達(dá)的基本形式[15]由局中人集合P、策略空間S和效用函數(shù)u這3個(gè)要素組成，即G={P,S,u}，其中，P= {P1, …,Pn}，

S={S1,… ,Sn}，u= {u1,… ,un}。效用函數(shù)ui:S→R（R代表實(shí)數(shù)空間），表示第i(i=1,2,…,n)個(gè)局中人在不同組合下所得的效益。

定義2納什均衡。對(duì)于博弈G={P,S,u}，如果由每個(gè)博弈方的一個(gè)策略所組成的策略組合中，任一博弈方Pi的策略都是應(yīng)對(duì)其他博弈方策略組合的最佳策略，即對(duì)于所有的存在博弈對(duì)于任意sij∈S，則稱為博弈G的一個(gè)納什均衡。

2.2 全同態(tài)加密

全同態(tài)加密方案一般由以下4個(gè)階段組成[16]。

加密階段c←EncryptFHE(P KE,m)：輸入公鑰PKE和需要加密的消息m，利用加密算法輸出一個(gè)對(duì)應(yīng)的密文。

解密階段m←DecryptFHE(S KE,c)：輸入私鑰SKE和需要解密的密文c，利用解密算法輸出一個(gè)對(duì)應(yīng)的明文。

運(yùn)算函數(shù)cf←EvalFHE(P KE,ci,f)：輸入公鑰PKE，加密的密文組ci和需要求值的函數(shù)f，利用運(yùn)算函數(shù)求解函數(shù)值。

其中，明文m= (m1,… ,mn)，密文c=(c1,…,cn)，密文組ci= (ci1,… ,cin)，函數(shù)值cf=f(ci)。

2.3 混淆電路

Yao的混淆電路[17]協(xié)議允許參與雙方在不對(duì)明文做任何加密的情況下，對(duì)明文進(jìn)行保密計(jì)算，該協(xié)議一般應(yīng)用于半誠實(shí)參與者之間，是確保雙方計(jì)算的通用方法。當(dāng)應(yīng)用在委托計(jì)算方案中時(shí)，委托方首先將委托的任意函數(shù)F轉(zhuǎn)換為布爾電路C，然后將轉(zhuǎn)換電路的混淆形式G(C)和委托方需要計(jì)算的函數(shù)x的混淆形式G(x)一起發(fā)送給計(jì)算方，這樣代表該布爾電路的每條輸入輸出線的隨機(jī)數(shù)均被加密。然后借助于準(zhǔn)備階段生成對(duì)應(yīng)電路C的混淆表進(jìn)行查表運(yùn)算，通過計(jì)算布爾電路的每個(gè)門得到整個(gè)電路的輸出。最后，計(jì)算方將計(jì)算結(jié)果的混淆形式G(F(x) )發(fā)送給對(duì)應(yīng)的委托方，委托方根據(jù)混淆電路將計(jì)算結(jié)果轉(zhuǎn)換為實(shí)際的輸出y。

圖1為混淆電路的結(jié)構(gòu)，其中X和Y為輸入線，Z為輸出線。這3根導(dǎo)線分別對(duì)應(yīng)有2個(gè)值：0和 1，即輸入線的輸入值和輸出線的輸出值。例如，當(dāng)輸入值a=0與b=1被選中后，混淆電路的任務(wù)就是需要安全地計(jì)算g(a,b)（g表示表 1中的輸出線）的值。混淆電路表如表1所示。

由表1可知，每個(gè)輸入輸出線X、Y、Z，且每根導(dǎo)線制定2個(gè)隨機(jī)值，對(duì)應(yīng)于0和1。由表1可知，需要使用混淆電路表將聯(lián)系起來，即在混淆電路表中，作為加密密鑰，在合適的密鑰輸入下對(duì)進(jìn)行加密，從而形成混淆電路。其中，當(dāng)給定2個(gè)輸入密鑰時(shí)，混淆計(jì)算表只有一行是可以正確解密的，即這樣可以有效地保證輸入信息的隱秘性。

圖1 混淆電路

表1 混淆電路表

在委托計(jì)算方案中，首先，委托方為每根導(dǎo)線選擇2個(gè)隨機(jī)密鑰，因此委托方共具有6個(gè)密鑰；其次，委托方對(duì)表1的每一行進(jìn)行加密，形成混淆電路表；接著，委托方將混淆電路表進(jìn)行重新隨機(jī)排列，這樣密鑰的位置就不會(huì)顯示與其有關(guān)聯(lián)的值，保證了密鑰的安全性?；煜娐繁硇纬珊螅蟹綄⒒煜娐繁戆l(fā)送給計(jì)算方，以及輸入計(jì)算值x和輸入密鑰由于計(jì)算方收到混淆電路表后，使用自己的密鑰來解密混淆電路表，所以，委托方必須將密鑰發(fā)給計(jì)算方。在此過程中，如果計(jì)算方將2個(gè)計(jì)算任務(wù)發(fā)送給委托方，那么計(jì)算方就可以解密更多信息，如果計(jì)算方要求委托方提供與其輸入相對(duì)應(yīng)的密鑰，那么委托方就可以學(xué)習(xí)計(jì)算方的輸入；為了避免信息的泄露，委托方與計(jì)算方使用不經(jīng)意傳輸協(xié)議，使委托方獲得與其在所有導(dǎo)線上的輸入相關(guān)聯(lián)的密鑰，以保證輸入輸出的隱私性；最后，計(jì)算方計(jì)算電路，并將輸出結(jié)果返回給委托方。

雖然混淆電路在委托計(jì)算方案中保護(hù)了客戶端的輸入輸出隱私，但多次使用混淆電路進(jìn)行計(jì)算時(shí)，惡意參與方可能將之前計(jì)算的標(biāo)簽輸出作為本次的輸出。結(jié)合全同態(tài)加密技術(shù)的混淆電路方法能夠解決混淆電路的重用問題，委托方利用全同態(tài)加密技術(shù)為每次委托計(jì)算的輸入選擇一個(gè)新的密鑰，以保證門電路信息不被泄露，從而解決了委托計(jì)算中混淆電路的重用問題。

2.4 可重用混淆電路

為解決混淆電路的重用問題，理性委托計(jì)算協(xié)議采用了隨機(jī)化混淆電路技術(shù)，該技術(shù)主要利用全同態(tài)加密同態(tài)性質(zhì)?？芍赜没煜娐贩桨钢校荑€串s∈ { 0 ,1}l，需要使用的公鑰是基于素?cái)?shù)階群q的元素向量；明文串x∈ { 0 ,1}n，其中，n=2l，l和n分別表示密鑰串長度和明文串的長度，密文也是基于素?cái)?shù)階群q的多個(gè)元素向量。利用全同態(tài)加密的同態(tài)性質(zhì)，通過群Zp上的 2個(gè)已知映射將0-1向量映射為同樣長度的0-1向量。

將需要使用的混淆電路進(jìn)行隨機(jī)化處理，即在圖1所示的布爾電路中，假設(shè)門電路g的第一根輸入導(dǎo)線的2個(gè)標(biāo)簽為A0和A1，第二根輸入導(dǎo)線的2個(gè)標(biāo)簽為B0和B1，輸出導(dǎo)線的2個(gè)標(biāo)簽為C0和C1。為了實(shí)現(xiàn)隨機(jī)化混淆，將每根導(dǎo)線隨機(jī)化選擇比特置換。假設(shè)將門電路g的第一根輸入導(dǎo)線的2個(gè)標(biāo)簽A0和A1進(jìn)行比特置換，其比特置換為θ和θ′，則輸入導(dǎo)線新標(biāo)簽為θ(A0)和θ(A1)。根據(jù)全同態(tài)加密的密鑰與明文的同態(tài)性質(zhì)，隨機(jī)選擇h、h′∈ ( 0 ,1)l，則密文EAa(h)變換為Eθ(Aa)(θ′(h) )。繼續(xù)選擇隨機(jī)數(shù)β∈ { 0 ,1}l，則形成的密文對(duì)為

由分析可知，通過為混淆電路的每根導(dǎo)線進(jìn)行比特置換，實(shí)現(xiàn)重新隨機(jī)化電路導(dǎo)線的標(biāo)簽和電路導(dǎo)線對(duì)應(yīng)的密文對(duì)，從而實(shí)現(xiàn)隨機(jī)化重復(fù)使用混淆電路的方法，且保證輸入輸出的隱私性。

2.5 理性委托計(jì)算

根據(jù)傳統(tǒng)的委托計(jì)算定義，結(jié)合Yao的混淆電路與全同態(tài)加密技術(shù)，引出理性委托計(jì)算定義。假設(shè)理性委托方將計(jì)算函數(shù)F委托給理性計(jì)算方，理性計(jì)算方根據(jù)其博弈模型及效用返回計(jì)算結(jié)果。理性委托計(jì)算方案RD的形式化描述由以下4個(gè)算法構(gòu)成。

1) K eyGen (F, 1λ)→ ( P K,SK)：將計(jì)算函數(shù)F用電路C來表示。根據(jù)Yao的混淆電路為每條導(dǎo)線隨機(jī)選擇2個(gè)值對(duì)于每個(gè)門電路g，計(jì)算其4個(gè)密文其中，公鑰PK為全部的密文集，即私鑰SK是其選擇的導(dǎo)線值，即

2) P roGenSK(x) →σx：運(yùn)行全同態(tài)加密算法，產(chǎn)生一個(gè)新的密鑰對(duì)，(S K,PK )← Setup (1λ)。

EEFHE令wi? S K 表示為輸入x的二進(jìn)制線值，且公共值為σx← (P KE,EncryptE( P KE,wi))，私有值為τx← S KE。

3) C omputePK(σx)→σy：計(jì)算Yao的混淆電路協(xié)議中的解密算法 D ecryptE(P KE,γi)，以獲得正確輸出線的標(biāo)簽，令σy為輸出線的標(biāo)簽。

4) R ecoverSK(σy) →y∪ ⊥：使用公鑰SK將輸出線標(biāo)簽σy中的導(dǎo)線值映射到輸出結(jié)果y的二進(jìn)制表示形式上。如果映射失敗，將輸出⊥，并令計(jì)算方接受相應(yīng)的懲罰。

定義3 正確性。如果問題生成算法生成的值使理性計(jì)算方輸出正確的值，則理性委托計(jì)算協(xié)議RD是正確的，其形式化表示如下。

對(duì)于任意x∈Domain(F)，如果 K eyGen(F,1λ)→(PK,SK)，ProGenSK(x)→σx和 C omputePK(σx)→σy都成立，且以不可忽略的概率使 R ecoverSK(σy)→(y=F(x) ,1)成立，則理性委托計(jì)算協(xié)議RD是正確的。

在協(xié)議中，若對(duì)于所有的概率多項(xiàng)式時(shí)間，敵手A不能使委托方接受一個(gè)不正確的輸出，則理性委托計(jì)算協(xié)議RD是安全的。

定義4 隱私性。理性委托計(jì)算協(xié)議RD的輸入輸出是隱私的，為理性委托計(jì)算協(xié)議RD定義敵手A，在協(xié)議中的優(yōu)勢(shì)為

在協(xié)議中，若對(duì)于任意的函數(shù)F和所有的概率

多項(xiàng)式時(shí)間敵手A，概率是可以忽略不計(jì)的，則理性委托計(jì)算協(xié)議RD是隱私的，其形式化分析如下

即如果存在2個(gè)不相同的輸入，產(chǎn)生的2個(gè)輸出結(jié)果以可忽略的概率區(qū)分，則理性委托計(jì)算協(xié)議RD是隱私的。

3 博弈分析及其安全模型

3.1 博弈模型分析

理性委托計(jì)算是將博弈論與委托計(jì)算結(jié)合的新型的委托計(jì)算方案，通過引入理性參與者，使用效用函數(shù)來保證計(jì)算結(jié)果的正確性。一般來說，在委托計(jì)算方案中，存在3種類型的計(jì)算方：誠實(shí)的計(jì)算方，誠實(shí)的計(jì)算方會(huì)完全按照委托方的要求進(jìn)行計(jì)算，并返回正確的結(jié)果；理性的計(jì)算方，理性計(jì)算方正確執(zhí)行計(jì)算任務(wù)的效用必須大于執(zhí)行其他任務(wù)的效用，如果在計(jì)算過程中懶惰計(jì)算的效用大于誠實(shí)計(jì)算，則理性計(jì)算方會(huì)選擇懶惰計(jì)算；惡意的計(jì)算方，惡意計(jì)算方將試圖破壞委托計(jì)算協(xié)議，并返回一個(gè)不正確的結(jié)果。實(shí)際上，由于協(xié)議中的參與者大多都是理性的，無論參與者是誠實(shí)或惡意的，在現(xiàn)實(shí)的協(xié)議中都是不合理的，因此，本文對(duì)理性的參與者進(jìn)行分析。

假設(shè)存在理性委托方1P和理性計(jì)算方2P，理性委托方有計(jì)算任務(wù)F，其計(jì)算任務(wù)的本身價(jià)值為Re。此時(shí)，理性計(jì)算方有“誠實(shí)”地返回正確結(jié)果和“惡意”地返回錯(cuò)誤結(jié)果這2種策略，即理性計(jì)算方P2的策略集為{誠實(shí),惡意}。當(dāng)理性計(jì)算方誠實(shí)地計(jì)算委托任務(wù)，其計(jì)算任務(wù)的成本為c( 1)，效用為u( 1)，返回正確答案后得到獎(jiǎng)勵(lì)為r，且獎(jiǎng)勵(lì)大于計(jì)算成本，即r＞c( 1)；若理性計(jì)算方存在惡意行為，則計(jì)算成本為c(q)，效用為u(q)，其中q為理性計(jì)算方作弊的概率，且u( 1)＞u(q)。

由于參與者都是理性的，此時(shí)理性委托方將根據(jù)理性計(jì)算方返回的計(jì)算結(jié)果選擇“獎(jiǎng)勵(lì)”誠實(shí)的理性計(jì)算方或者“懲罰”惡意的理性計(jì)算方，即理性委托方1P的策略集為{懲罰, 不懲罰}。但當(dāng)理性委托方未按照約定對(duì)理性計(jì)算方進(jìn)行獎(jiǎng)勵(lì)，理性計(jì)算方可向可信第三方提出申訴，并對(duì)理性委托方進(jìn)行罰款，記該罰款為Q1；同理，理性計(jì)算方存在惡意行為返回不正確的答案，理性委托方將對(duì)其進(jìn)行懲罰，記該罰款為Q2。

基于對(duì)博弈模型的分析，可以得到理性參與者的效用矩陣。根據(jù)理性計(jì)算方的行為策略和理性委托方的行為策略，可以得到相應(yīng)的效用矩陣，如表2所示。

表2 理性委托計(jì)算參與者的效用矩陣

根據(jù)理性參與者的行為策略分析，理性委托計(jì)算可以分為3個(gè)階段進(jìn)行。

1) 理性委托方1P對(duì)于計(jì)算任務(wù)F，可以選擇自己計(jì)算，或者選擇委托給計(jì)算能力強(qiáng)大的服務(wù)器，即理性計(jì)算方2P進(jìn)行計(jì)算。

2) 理性計(jì)算方2P對(duì)于計(jì)算任務(wù)F，從策略集{誠實(shí), 惡意}中選擇一種策略進(jìn)行反饋。

3) 理性委托方1P根據(jù)理性計(jì)算方2P反饋的結(jié)果，從策略集{懲罰, 不懲罰}中選擇一種策略進(jìn)行反饋。

將博弈論引入本協(xié)議中，利用子博弈精煉納什均衡來分析理性委托計(jì)算。在每個(gè)階段中，對(duì)應(yīng)的參與方都有行為策略進(jìn)行對(duì)應(yīng)，例如，理性計(jì)算方2P“惡意”地返回錯(cuò)誤結(jié)果，則理性委托方1P會(huì)選擇懲罰理性計(jì)算方2P，即該策略組合可以達(dá)到納什均衡狀態(tài)，其理性委托方與理性計(jì)算方的策略與效用用博弈樹來表示，如圖2和圖3所示。

圖2 理性計(jì)算方的效用博弈樹

圖3 理性委托方的效用博弈樹

3.2 安全模型

根據(jù)上述的博弈分析，給出了基于全同態(tài)加密與隨機(jī)化混淆電路相結(jié)合的理性委托計(jì)算安全模型。對(duì)真實(shí)實(shí)驗(yàn)中與理想實(shí)驗(yàn)中輸出結(jié)果進(jìn)行分析，如果任意概率多項(xiàng)式時(shí)間的區(qū)分器不能區(qū)分這 2個(gè)實(shí)驗(yàn)結(jié)果，則本實(shí)驗(yàn)是安全的，滿足語義安全。此安全模型用于抵御惡意敵手的多項(xiàng)式次查詢，保證委托計(jì)算輸入輸出的隱私性及委托計(jì)算結(jié)果的正確性。

1) 理性委托計(jì)算理想實(shí)驗(yàn)下的安全模型

理想實(shí)驗(yàn)挑戰(zhàn)者與仿真器S。

初始化階段挑戰(zhàn)者將安全參數(shù)1λ發(fā)送給仿真器。

挑戰(zhàn)階段敵手向挑戰(zhàn)者發(fā)送有效的明文概率分布wi，挑戰(zhàn)者根據(jù)概率分布wi隨機(jī)選擇 2個(gè)明文wi0和wi1。

解密階段仿真器隨機(jī)選擇b∈ { 0 ,1}，將其發(fā)送給挑戰(zhàn)者。挑戰(zhàn)者打開對(duì)應(yīng)的明文分量得到(wi)i∈b，然后將明文分量發(fā)送給仿真器。

輸出階段仿真器調(diào)用解密算法σy←DecryptE(P KE,wi)得到解密結(jié)果，并輸出解密結(jié)果σy。

2) 理性委托計(jì)算真實(shí)實(shí)驗(yàn)下的安全模型

真實(shí)實(shí)驗(yàn)挑戰(zhàn)者與敵手。

初始化階段挑戰(zhàn)者調(diào)用密鑰生成算法KeyGen( 1λ,F)→ ( P K,SK)得到公鑰私鑰對(duì)，并將公鑰PK發(fā)送給敵手。

解密階段1 敵手查詢密文γi，挑戰(zhàn)者調(diào)用解密算法 D ecryptE(P KE,γi)進(jìn)行回復(fù)。

挑戰(zhàn)階段敵手向挑戰(zhàn)者提交 2個(gè)長度相同的明文消息w0和w1，挑戰(zhàn)者隨機(jī)選擇一個(gè)比特b，其中b∈ { 0,1}，調(diào)用加密算法加密wb，從而得到挑戰(zhàn)密文。挑戰(zhàn)者將得到的挑戰(zhàn)密文發(fā)送給敵手。

解密階段2 敵手查詢密文σx，其中σx≠σx?。挑戰(zhàn)者繼續(xù)調(diào)用解密算法σy←DecryptE(P KE,wi)得到解密結(jié)果σy。

輸出階段挑戰(zhàn)者將結(jié)果yσ發(fā)送給敵手，敵手猜測(cè)b的值b′。

若敵手猜出bb′= ，則敵手贏得本次比賽。

4 理性委托計(jì)算方案構(gòu)造

本節(jié)結(jié)合混淆電路與全同態(tài)加密技術(shù)，設(shè)計(jì)可重用的理性委托計(jì)算協(xié)議。在協(xié)議中，假設(shè)理性委托方P1將需要計(jì)算的函數(shù)F秘密地發(fā)送給理性計(jì)算方P2，只有當(dāng)理性參與者發(fā)送正確的結(jié)果，才能使自己得到的效用最大；若理性參與者存在欺騙行為，則會(huì)受到遠(yuǎn)大于計(jì)算成本的懲罰。方案中λ為安全參數(shù)，執(zhí)行計(jì)算函數(shù)F任務(wù)所需時(shí)間為t，具體如下。

初始化階段

首先，理性委托方P1將計(jì)算函數(shù)F轉(zhuǎn)換為布爾電路C，并生成混淆電路G(C)。根據(jù)Yao的混淆電路的構(gòu)造，為每個(gè)電路導(dǎo)線wi隨機(jī)選擇 2個(gè)值，對(duì)于每個(gè)門電路g，計(jì)算其4個(gè)密文。每個(gè)門電路的公鑰PK為密文組集合，即，私鑰SK是其選擇的導(dǎo)線值，即

然后，協(xié)議將執(zhí)行全同態(tài)加密算法，首先由密鑰生成算法生成一個(gè)新的密鑰對(duì)(S KE, PKE)。在此過程中將隨機(jī)選擇的導(dǎo)線wi表示為輸入x的二進(jìn)制線值。利用全同態(tài)加密的密鑰對(duì)將輸入線值進(jìn)行編碼，其公有編碼值為σx←(PKE,EncryptE(PKE,wi))。

最后，理性委托方P1把混淆電路G(C)和輸入x的編碼一起發(fā)送給接受計(jì)算任務(wù)的理性計(jì)算方P2，以便理性計(jì)算方在沒有理性委托方存在的情況下獲得G(x)關(guān)于x的任何信息，從而保證輸入的安全性。

委托計(jì)算階段

理性計(jì)算方P2接收到計(jì)算任務(wù)后，根據(jù)輸入導(dǎo)線w、w′、γ和輸出導(dǎo)線Dw(Dw′(γ))構(gòu)建電路Δ，其中Dw為Yao的混淆電路中加密算法E對(duì)應(yīng)的解密算法。根據(jù)Yao的混淆電路，計(jì)算方解析收到的輸入編碼σx。由解密算法DecryptE(PKE,γi)得到布爾電路正確的輸出線的標(biāo)簽σy。其中σy←DecryptE為二進(jìn)制中表示y=F(x)的線值。理性計(jì)算方將得到的計(jì)算結(jié)果作為輸出返還給理性委托方P1。

支付效用階段

理性委托方P1接收到計(jì)算結(jié)果σy后，首先利用同態(tài)加密算法的私鑰SKE解密σy←EncryptE來獲得然后使用公鑰SK將輸出線標(biāo)簽σy中的導(dǎo)線值映射到輸出結(jié)果y的二進(jìn)制表示形式上。

如果y=F(x)，理性委托方P1需根據(jù)約定在時(shí)間t內(nèi)將獎(jiǎng)勵(lì)金r支付給理性計(jì)算方P2，此時(shí)理性委托方的效用為Re-r，理性計(jì)算方的效用為r-c( 1)。

如果映射失敗，即y≠F(x)，理性委托方P1將會(huì)對(duì)理性計(jì)算方P2進(jìn)行懲罰，罰金為Q2。此時(shí)理性委托方的效用為Re- (rq-Q2(1 -q) -c(q))，理性計(jì)算方的效用為rq-Q2(1-q) -c(q)。

由博弈分析可知，只有當(dāng)理性委托方和理性計(jì)算方都選擇誠實(shí)的行為策略時(shí)，他們的效益才最大，此時(shí)該策略組合也可以達(dá)到納什均衡。

5 安全性分析

定理1 在 DDH（decision Diffie-Hellman）假設(shè)下，本文所提的理性委托計(jì)算協(xié)議是語義安全的。

證明本文所提理性委托計(jì)算協(xié)議是在 DDH假設(shè)下，以全同態(tài)加密與隨機(jī)化混淆電路技術(shù)為基礎(chǔ)的。在分析其安全性時(shí)，如果2次輸入執(zhí)行的猜測(cè)結(jié)果是以不可忽略的概率分辨的，則定理的結(jié)果成立。

假設(shè)存在概率多項(xiàng)式時(shí)間（PPT, probabilistic polynomial time）敵手A，其安全參數(shù)為λ，有不可忽略的δ，且

在協(xié)議中，定義L為敵手A執(zhí)行查詢的上限。且在理性委托計(jì)算的過程中，隨機(jī)化混淆電路的門電路會(huì)隨機(jī)生成，因此敵手A不能因?yàn)槎啻螆?zhí)行查詢而學(xué)習(xí)標(biāo)簽的相關(guān)情況，如果敵手A在游戲中獲得勝利，則必須是一次性查詢就獲得成功。

假設(shè)敵手A在第i次執(zhí)行時(shí)獲得成功，其中，1≤i≤L，則Hi(R D,F,λ)=1；如果執(zhí)行失敗，A則表示為

在協(xié)議執(zhí)行過程中，如果敵手A在第i+1次執(zhí)行時(shí)獲得成功，則敵手A猜測(cè)的計(jì)算輸入為Ai+1；如果執(zhí)行失敗，敵手A猜測(cè)的計(jì)算輸入為Ai。因此敵手A在2次實(shí)驗(yàn)過程中有可忽略的概率區(qū)分，具體如下。

其中，p是一個(gè)多項(xiàng)式，且對(duì)任意多項(xiàng)式時(shí)間敵手A有

在上述的實(shí)驗(yàn)中的優(yōu)勢(shì)為

在協(xié)議中，若對(duì)于所有的概率多項(xiàng)式時(shí)間敵手A，概率 A DVVerif(R D,F,λ)是可以忽略不計(jì)的，

RD則理性委托計(jì)算協(xié)議RD是安全的，即敵手A在2次實(shí)驗(yàn)中以可以忽略的概率區(qū)分 2次猜測(cè)結(jié)果，因此，上述理性委托計(jì)算協(xié)議是語義安全的。在存在惡意參與方的情況下，理性計(jì)算方無法獲得關(guān)于輸入w和輸出σy的任何信息，則可以保證委托方的輸入輸出隱私。

證畢。

定理2 根據(jù)設(shè)計(jì)的理性委托計(jì)算協(xié)議，當(dāng)理性參與者都選擇誠實(shí)策略時(shí)，協(xié)議可以滿足納什均衡狀態(tài)，即全局可以達(dá)到效益最優(yōu)。

證明在協(xié)議的初始化階段，如果理性委托方P1和理性計(jì)算方P2都遵守協(xié)議規(guī)則，雙方將會(huì)選擇最有利的行為策略。理性計(jì)算方P2在其計(jì)算能力范圍內(nèi)接受理性委托方P1發(fā)送的計(jì)算任務(wù)G(C)和輸入x。

在委托計(jì)算階段，理性計(jì)算方P2在時(shí)間t內(nèi)將計(jì)算結(jié)果σy← D ecryptE(P KE,wi)作為計(jì)算輸出發(fā)送給理性委托方P1。此時(shí)需要考慮理性參與者選擇的行為策略，若理性委托方與理性計(jì)算方都采取誠實(shí)策略，理性委托方就可得到R-r的效用，理性計(jì)算方也可得到r-c( 1)的效用；若理性委托方選擇誠實(shí)策略，按時(shí)將獎(jiǎng)勵(lì)金返回給理性計(jì)算方，而理性計(jì)算方選擇惡意策略，理性委托方就可得到Re- (rq-Q2(1 -q) -c(q))的效用，理性計(jì)算方也可得到rq-Q2(1 -q) -c(q)的效用；若理性委托方選擇惡意策略，沒有將獎(jiǎng)勵(lì)金返回給計(jì)算方，而理性計(jì)算方選擇誠實(shí)策略，理性委托方就可得到Re-Q1的效用，理性計(jì)算方也可得到r-c( 1)+Q1的效用；如果理性委托方和計(jì)算方都選擇惡意策略欺騙對(duì)方，理性委托方就可得到Re-Q1的效用，理性計(jì)算方也可得到rq-Q2(1 -q) -c(q)的效用。

在支付效用階段，由于在博弈模型中獎(jiǎng)勵(lì)金大于計(jì)算成本，即r＞c( 1)，且其效用有u( 1)＞u(q)，罰金Q1與Q2也遠(yuǎn)大于計(jì)算成本。所以只有當(dāng)理性參與方都選擇誠實(shí)的策略時(shí)，理性委托方P1和理性計(jì)算方P2才能得到最大的效用，此時(shí)全局狀態(tài)也達(dá)到最優(yōu)。

證畢。

根據(jù)協(xié)議的分析可知，用子博弈精煉納什均衡來分析理性委托計(jì)算，只有當(dāng)理性參與方都選擇誠實(shí)策略時(shí)，全局才可以達(dá)到最優(yōu)狀態(tài)，執(zhí)行協(xié)議結(jié)束，即該協(xié)議具有正確性，且滿足納什均衡狀態(tài)。

6 仿真實(shí)驗(yàn)與性能分析

6.1 仿真實(shí)驗(yàn)

針對(duì)本文所提的可證明安全的理性委托計(jì)算協(xié)議，將不同數(shù)量的模指數(shù)運(yùn)算委托出去后引入本模型中，使用本文所提理性委托計(jì)算協(xié)議，理性委托方不需要對(duì)返回結(jié)果進(jìn)行驗(yàn)證，委托計(jì)算所需時(shí)間對(duì)比如圖4所示。由圖4可知，用戶通過理性委托計(jì)算所消耗時(shí)間比直接計(jì)算和委托計(jì)算消耗時(shí)間都要少，并且當(dāng)委托數(shù)量增大時(shí)，3種方式所需時(shí)間的差距也在增大，而理性委托計(jì)算的計(jì)算效率也更高。

圖4 委托計(jì)算不同模型的時(shí)間開銷

6.2 性能分析

本文提出的理性委托計(jì)算協(xié)議與現(xiàn)有的委托計(jì)算協(xié)議進(jìn)行比較，具體如表3所示。從委托計(jì)算的計(jì)算復(fù)雜度、通信復(fù)雜度、可證明安全等方面進(jìn)行對(duì)比。其中，“√”表示滿足該性能，“×”表示不能滿足性能。

Kupcu等[18]提出了一種理性的委托計(jì)算協(xié)議，該協(xié)議激勵(lì)所有的理性計(jì)算方正確地執(zhí)行委托任務(wù)，但不關(guān)心計(jì)算任務(wù)或數(shù)據(jù)的隱藏，只關(guān)心計(jì)算結(jié)果的正確性，其計(jì)算復(fù)雜度為O(1)，通信復(fù)雜度為1，未能滿足可證明安全的性能。

表3 本文協(xié)議與其他協(xié)議性能對(duì)比

Chen等[19]提出了在分布式環(huán)境中將計(jì)算任務(wù)委托給不受信任的計(jì)算方，利用新的公平有條件支付方案解決委托方與不誠實(shí)的計(jì)算方之間的信任問題。該協(xié)議的計(jì)算復(fù)雜度為O(1)，通信復(fù)雜度為1。但該方案未能對(duì)安全性進(jìn)行有效的證明，未能滿足可證明安全的性能。

Gennaro等[20]提出了基于Yao的混淆電路與全同態(tài)加密技術(shù)構(gòu)造可驗(yàn)證的委托計(jì)算協(xié)議，該協(xié)議雖然將計(jì)算任務(wù)委托給不受信任的計(jì)算方，但能保證參與者輸入和輸出的隱私。該協(xié)議雖然滿足了可證明安全的性能，但由于方案中需要驗(yàn)證計(jì)算結(jié)果的正確性，所需的計(jì)算復(fù)雜度為通信復(fù)雜度至少為2，因此性能較低。

本文協(xié)議是基于 Yao的混淆電路技術(shù)和全同態(tài)加密技術(shù)構(gòu)造的理性委托計(jì)算協(xié)議。在協(xié)議中構(gòu)造委托計(jì)算博弈模型，取消了委托方對(duì)結(jié)果的驗(yàn)證過程，而是通過參與者的效用函數(shù)保證計(jì)算結(jié)果的正確性。只要參與者遵守協(xié)議，最終他們都能獲得最大的收益，并能達(dá)到最終的納什均衡狀態(tài)。本文協(xié)議的計(jì)算復(fù)雜度為O(1)，通信復(fù)雜度為1，且滿足可證明安全的性能。

7 結(jié)束語

本文引入了理性委托計(jì)算的概念，將計(jì)算任務(wù)委托給不受信任的服務(wù)器，并詳細(xì)分析了在博弈論框架下委托計(jì)算中各參與方的效用及策略，設(shè)計(jì)了可證明安全的理性委托計(jì)算協(xié)議，該協(xié)議將Yao的混淆電路與全同態(tài)加密方案相結(jié)合，即使協(xié)議中存在惡意的敵手也能保證高效的委托。該協(xié)議也保證了委托方的輸入輸出隱私安全，以及輸出結(jié)果的正確性。本文是基于Yao的混淆電路與全同態(tài)加密方案設(shè)計(jì)了可證明安全的理性委托計(jì)算協(xié)議，而將計(jì)算任務(wù)委托給比全同態(tài)加密更有效的委托計(jì)算方案中，這將是下一步要研究的工作。