可證明安全的理性委托計算協議

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

（1. 貴州大學計算機科學與技術學院，貴州 貴陽 550025；2. 貴州省公共大數據重點實驗室，貴州 貴陽 550025；3. 貴州大學數學與統計學院，貴州 貴陽 550025）

1 引言

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

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

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

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

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

2) 根據構建的委托計算博弈模型中納什均衡需求，以及理性委托計算的安全需求，設計了可證明安全的理性委托計算安全模型。

3) 利用隨機化混淆電路可重用的優點與全同態加密技術，保證了理性參與者結果的正確性及委托計算輸入和輸出隱私，從而構建了安全的理性委托計算協議。

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

2 基礎知識

2.1 博弈論

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

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

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

2.2 全同態加密

全同態加密方案一般由以下4個階段組成[16]。

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

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

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

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

2.3 混淆電路

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

圖1為混淆電路的結構，其中X和Y為輸入線，Z為輸出線。這3根導線分別對應有2個值：0和 1，即輸入線的輸入值和輸出線的輸出值。例如，當輸入值a=0與b=1被選中后，混淆電路的任務就是需要安全地計算g(a,b)（g表示表 1中的輸出線）的值。混淆電路表如表1所示。

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

圖1 混淆電路

表1 混淆電路表

在委托計算方案中，首先，委托方為每根導線選擇2個隨機密鑰，因此委托方共具有6個密鑰；其次，委托方對表1的每一行進行加密，形成混淆電路表；接著，委托方將混淆電路表進行重新隨機排列，這樣密鑰的位置就不會顯示與其有關聯的值，保證了密鑰的安全性。混淆電路表形成后，委托方將混淆電路表發送給計算方，以及輸入計算值x和輸入密鑰由于計算方收到混淆電路表后，使用自己的密鑰來解密混淆電路表，所以，委托方必須將密鑰發給計算方。在此過程中，如果計算方將2個計算任務發送給委托方，那么計算方就可以解密更多信息，如果計算方要求委托方提供與其輸入相對應的密鑰，那么委托方就可以學習計算方的輸入；為了避免信息的泄露，委托方與計算方使用不經意傳輸協議，使委托方獲得與其在所有導線上的輸入相關聯的密鑰，以保證輸入輸出的隱私性；最后，計算方計算電路，并將輸出結果返回給委托方。

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

2.4 可重用混淆電路

為解決混淆電路的重用問題，理性委托計算協議采用了隨機化混淆電路技術，該技術主要利用全同態加密同態性質。可重用混淆電路方案中，密鑰串s∈ { 0 ,1}l，需要使用的公鑰是基于素數階群q的元素向量；明文串x∈ { 0 ,1}n，其中，n=2l，l和n分別表示密鑰串長度和明文串的長度，密文也是基于素數階群q的多個元素向量。利用全同態加密的同態性質，通過群Zp上的 2個已知映射將0-1向量映射為同樣長度的0-1向量。

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

由分析可知，通過為混淆電路的每根導線進行比特置換，實現重新隨機化電路導線的標簽和電路導線對應的密文對，從而實現隨機化重復使用混淆電路的方法，且保證輸入輸出的隱私性。

2.5 理性委托計算

根據傳統的委托計算定義，結合Yao的混淆電路與全同態加密技術，引出理性委托計算定義。假設理性委托方將計算函數F委托給理性計算方，理性計算方根據其博弈模型及效用返回計算結果。理性委托計算方案RD的形式化描述由以下4個算法構成。

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

2) P roGenSK(x) →σx：運行全同態加密算法，產生一個新的密鑰對，(S K,PK )← Setup (1λ)。

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

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

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

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

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

在協議中，若對于所有的概率多項式時間，敵手A不能使委托方接受一個不正確的輸出，則理性委托計算協議RD是安全的。

定義4 隱私性。理性委托計算協議RD的輸入輸出是隱私的，為理性委托計算協議RD定義敵手A，在協議中的優勢為

在協議中，若對于任意的函數F和所有的概率

多項式時間敵手A，概率是可以忽略不計的，則理性委托計算協議RD是隱私的，其形式化分析如下

即如果存在2個不相同的輸入，產生的2個輸出結果以可忽略的概率區分，則理性委托計算協議RD是隱私的。

3 博弈分析及其安全模型

3.1 博弈模型分析

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

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

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

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

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

根據理性參與者的行為策略分析，理性委托計算可以分為3個階段進行。

1) 理性委托方1P對于計算任務F，可以選擇自己計算，或者選擇委托給計算能力強大的服務器，即理性計算方2P進行計算。

2) 理性計算方2P對于計算任務F，從策略集{誠實, 惡意}中選擇一種策略進行反饋。

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

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

圖2 理性計算方的效用博弈樹

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

3.2 安全模型

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

1) 理性委托計算理想實驗下的安全模型

理想實驗挑戰者與仿真器S。

初始化階段挑戰者將安全參數1λ發送給仿真器。

挑戰階段敵手向挑戰者發送有效的明文概率分布wi，挑戰者根據概率分布wi隨機選擇 2個明文wi0和wi1。

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

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

2) 理性委托計算真實實驗下的安全模型

真實實驗挑戰者與敵手。

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

解密階段1 敵手查詢密文γi，挑戰者調用解密算法 D ecryptE(P KE,γi)進行回復。

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

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

輸出階段挑戰者將結果yσ發送給敵手，敵手猜測b的值b′。

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

4 理性委托計算方案構造

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

初始化階段

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

然后，協議將執行全同態加密算法，首先由密鑰生成算法生成一個新的密鑰對(S KE, PKE)。在此過程中將隨機選擇的導線wi表示為輸入x的二進制線值。利用全同態加密的密鑰對將輸入線值進行編碼，其公有編碼值為σx←(PKE,EncryptE(PKE,wi))。

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

委托計算階段

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

支付效用階段

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

如果y=F(x)，理性委托方P1需根據約定在時間t內將獎勵金r支付給理性計算方P2，此時理性委托方的效用為Re-r，理性計算方的效用為r-c( 1)。

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

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

5 安全性分析

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

證明本文所提理性委托計算協議是在 DDH假設下，以全同態加密與隨機化混淆電路技術為基礎的。在分析其安全性時，如果2次輸入執行的猜測結果是以不可忽略的概率分辨的，則定理的結果成立。

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

在協議中，定義L為敵手A執行查詢的上限。且在理性委托計算的過程中，隨機化混淆電路的門電路會隨機生成，因此敵手A不能因為多次執行查詢而學習標簽的相關情況，如果敵手A在游戲中獲得勝利，則必須是一次性查詢就獲得成功。

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

在協議執行過程中，如果敵手A在第i+1次執行時獲得成功，則敵手A猜測的計算輸入為Ai+1；如果執行失敗，敵手A猜測的計算輸入為Ai。因此敵手A在2次實驗過程中有可忽略的概率區分，具體如下。

其中，p是一個多項式，且對任意多項式時間敵手A有

在上述的實驗中的優勢為

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

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

證畢。

定理2 根據設計的理性委托計算協議，當理性參與者都選擇誠實策略時，協議可以滿足納什均衡狀態，即全局可以達到效益最優。

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

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

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

證畢。

根據協議的分析可知，用子博弈精煉納什均衡來分析理性委托計算，只有當理性參與方都選擇誠實策略時，全局才可以達到最優狀態，執行協議結束，即該協議具有正確性，且滿足納什均衡狀態。

6 仿真實驗與性能分析

6.1 仿真實驗

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

圖4 委托計算不同模型的時間開銷

6.2 性能分析

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

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

表3 本文協議與其他協議性能對比

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

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

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

7 結束語

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