基于可重隨機化混淆電路的可驗證計算?

趙青松,曾慶凱,劉西蒙,徐煥良

1(計算機軟件新技術國家重點實驗室(南京大學),江蘇 南京 210023)

2(南京大學 計算機科學與技術系,江蘇 南京 210023)

3(福州大學 數學與計算機科學學院,福建 福州 350117)

4(School of Information Systems,Singapore Management University,Singapore 178902,Singapore)

5(南京農業大學 信息科技學院,江蘇 南京 210095)

1 引 言

可驗證計算可使計算能力較弱的客戶端將函數計算外包給計算能力強但不被信任的服務器,服務器返回計算結果以及計算正確執行的證據,并要求客戶端驗證此證據的開支必須比自己重新計算函數的開支要小.另外,可驗證計算也需要保證隱私性,即服務器對客戶端輸入(也可以包括輸出)一無所知.Kilian在早期關于有效論證(argument)[1]和Micali的計算正確證明(computationally sound proof,簡稱CS Proof)[2]中都提出了計算雙方交互只有1輪的非交互可驗證計算.Gennaro等人形式化定義和構造了客戶端和服務器之間的非交互可驗證計算方案[3].隨后,在非交互可驗證計算方面的許多工作也提出了很多安全外包任意函數的密碼方案[4-12].

Yao的混淆電路(Yao’s garbled circuit)是一種實現半誠實敵手下的安全兩方計算經典和有效的手段[13,14],但是混淆電路存在電路只能使用 1次的基本限制,為電路提供超過 1次的編碼輸入會損害混淆電路的保密性.Goldwasser等人采用全同態加密(fully homomorphic encryption,簡稱FHE)的方法首次構造了用于兩方計算的可重用混淆電路.困難性假設是誤差學習(learning with error,簡稱LWE)假設,不過,該構造只達到選擇(selective)安全[15].Agrawal也采用 FHE基于 LWE假設構造安全性更強的半適應性(semi-adaptive)安全可重用混淆電路[16].在可驗證計算背景下,客戶端可以采用Yao的混淆電路將只有客戶端輸入的函數外包給不信任的服務器.但是,用于可驗證計算的混淆電路也存在電路只能使用一次的基本限制.組合使用FHE和混淆電路可使客戶端和服務器實現多項式次數輸入的混淆電路重用[3].然而,該方案只在敵手不能對客戶端發起任何數量的驗證查詢(verification query)這種較弱的模型下被證明是安全的.同樣地,為了滿足安全的需要,許多其他的可驗證計算解決方案也是依賴于FHE的[5,7,9,10].

盡管理論上基于 FHE的可驗證計算是可能的,但實際上因為所用的 FHE方案效率十分低下[17],所以基于FHE的可驗證計算構造實際運行開支都很高,且通常需客戶端和服務器都執行 FHE,這對于計算能力較弱的客戶端,甚至對于計算能力強大的服務器來說,都是很重的負擔.

采用密碼方法解決可驗證計算都需要特定的密碼困難性假設.Brakerski等人提出了基于LWE假設的限層全同態加密(leveled fully homomorphic encryption)[18],這是基于格的公鑰加密最好的已知困難性假設.但是,所有標準(非限層)FHE的假設都需要更強的環安全(circular security)假設.因此,我們有興趣構造可驗證計算協議,使其所基于的困難性假設盡可能地弱,這樣,如果其中的原語(primitive)被證明對新的攻擊是脆弱的,或者新出現的原語具有更好的性能,那么協議所使用的原語就要被替換.

1.1 本文貢獻

在本文中,我們將首先構造一個采用加同態加密的非交互可驗證計算協議.它是基于 DDH假設,在任意新輸入下能夠實現客戶端基于混淆電路的外包計算,可以容忍多項式次數的惡意驗證查詢,并為提供客戶端的輸入輸出隱私保護,以及函數計算的正確性和語義的安全性.

客戶端可使用 Yao的混淆電路,將只有客戶端輸入的函數計算外包給服務器,但在新輸入下重用電路是不安全的.這是因為電路的輸出標簽一旦泄露,服務器就可能使用這些標簽作為下次外包計算的結果輸出.本文解決這個問題的主要方法是可重隨機化的混淆電路(re-randomizable garbled circuit),其可實現客戶端使用隨機數r產生的混淆電路,以及服務器根據此混淆電路和客戶端給定的隨機數r′(affine transformations,也就是映射轉換)產生的重隨機化混淆電路(re-randomized garbled circuit),計算能力有限的敵手將不能區分它們[19,20],這意味著原混淆電路和重隨機化電路的分布是計算上不可區分的.

然而,由于以下兩個因素,可重隨機化的混淆電路并不能直接用于可驗證計算.

· 首先,服務器產生重隨機化混淆電路之后,客戶端將函數輸入重隨機化后發給服務器,服務器就可以根據此重隨機化輸入逐個門電路(gate by gate)檢查重隨機化混淆電路,最終得到重隨機化的輸出.但是,由客戶端給定的映射轉換和重隨機化輸入,服務器會獲取原混淆電路的有價值信息.

· 其次,重隨機化混淆電路的構造過程僅在半誠實模型下是安全的,易受到來自行為可以表現為任何方式的惡意敵手攻擊.例如,如果一個惡意的服務器使用同樣的映射轉換重復重隨機化混淆電路,服務器就有可能使用重隨機化混淆電路超過1次.

重隨機化混淆電路過程的有效性證明是典型的零知識(或證據不可區分)證明.一般地,可以使用隨機預言機模式經 Fiat-Shamir范式獲取有效的非交互零知識證明[11,20].為了優化針對惡意敵手的協議,本文將采用第 3節的方法,不使用Fiat-Shamir范式,實現惡意敵手下的安全重隨機化混淆電路,從而使協議更簡潔.

為了能夠將可重隨機化的混淆電路應用于可驗證計算,采用的主要技術手段是數學隱藏方法(mathematical disguise method)[21]和Kilian的隨機化技術(Kilian’s randomization technique)[22].數學隱藏方法使服務器在重復隨機化混淆電路過程中不能重用映射轉換,以及客戶端的開銷與函數的計算開支無關.Kilian的隨機化技術隨機隱藏映射轉換的每個部分,從而確保服務器按序重隨機化電路.該技術手段可以抵御混合輸入攻擊(mixedinput attack)和部分計算攻擊(partial evaluation attack).此外,由于上述可驗證計算協議是靜態(static)安全的,因此,我們還給出了該協議實現適應性(adaptive)安全的方法.

在本文的最后部分,將上述構造應用于密碼轉置防火墻(cryptographic reverse firewall)[23],給出一種不采用FHE安全兩方計算下的混淆電路重用方法.密碼轉置防火墻可被解釋為一種狀態算法,該算法能夠處理安裝防火墻的用戶發送和接收的已由某些密碼算法處理的消息.一方面,如果原有實現已被破壞,則密碼轉置防火墻將恢復其安全性;另一方面,如果原有實現是正確的,但密碼轉置防火墻是不安全的,此時密碼轉置防火墻并不比任何主動敵手更具破壞性.例如,利用某些特定的協議性質,它能夠掛起拒絕服務攻擊,如丟掉一些消息.從這個角度來說,不必比傳播媒介更信任密碼轉置防火墻.

密碼轉置防火墻的關鍵技術是可重隨機化的不經意傳輸(re-randomizable oblivious transfer)和可重隨機化的混淆電路.然而,密碼轉置防火墻重隨機化混淆電路超過1次是不安全的.為了打破該局限,也是作為上述構造的一個應用,本文提出一種新的密碼轉置防火墻模型——可重用密碼轉置防火墻,用戶生成混淆電路 1次,然后可重用轉置密碼防火墻可安全的重隨機化混淆電路多次.

2 預備知識

2.1 可驗證計算定義

遵循文獻[3,10],下面介紹非交互可驗證計算定義.假設客戶端將函數f計算外包給服務器,然后服務器返回計算結果和計算正確執行的證據.可驗證計算方案VC的形式化描述由以下4種算法組成.

·KeyGen(1,f)→(pk,sk).隨機化密碼生成算法將安全參數和函數f作為輸入,生成公鑰pk和私鑰sk,客戶端將公鑰發送給服務器,私鑰由客戶端秘密保存.

·ProbGen(sk,x)→(σx,τx).問題生成算法將密鑰sk和客戶端的函數輸入x作為輸入,輸出x的編碼輸入σx和秘密值τx.σx由客戶端發送給服務器用于計算,τx由客戶端用于驗證.

·Compute(pk,σx)→(σy):給定公鑰pk和編碼輸入σx,服務器運行該算法計算函數f輸出y=f(x)的編碼形式σy.

·Verify(sk,σy,τx)→(acc,y).輸入密鑰sk和秘密值τx,客戶端執行驗證算法.該算法將服務器的編碼輸出σy轉換成一個比特acc和一個字符串y.如果acc=1,客戶端就接受計算結果y=f(x);如果acc=0,客戶端就拒絕接受計算結果.

若惡意的服務器輸入由算法ProbGen生成的σx,執行算法Compute產生的結果不能被驗證成功且與函數f在輸入x的計算結果不一致,則該可驗證計算方案VC是正確的.

定義1(正確性).?x∈Domain(f),?f∈F,其中,F是一個函數族,若(pk,sk)←KeyGen(1,f),(σx,τx)←ProbGen(sk,x),(σy)←Compute(pk,σx),則(1,y=f(x))←Verify(sk,σy,τx)以不可忽略的概率成立,那么該可驗證計算方案VC是正確的.

若敵手不能使驗證算法接受一個不正確的輸出,則可驗證計算方案VC是安全的.也就是說,對于函數f和輸入x,若,則Verify不能輸出.

考慮關于敵對的服務器A的如下實驗.

其中,預言機PVerify(σ,τ)返回acc,當且僅當表示敵手A的 PVerify 查詢.

上述實驗中,敵手通過訪問預言機生成多個問題實例,并檢查客戶端對任意編碼的響應.若給定一個輸入值,敵手產生輸出使驗證算法接受該錯誤的輸出值,則敵手成功.

定義2(安全性).為可驗證計算方案VC定義敵手A,其在上述實驗中的優勢為

輸入(輸出)隱私的定義采用不可區分方法以確保沒有輸入(輸出)信息泄露.由輸入隱私立即得到輸出隱私.若有兩個不同的輸入,問題生成算法ProbGen產生的兩個輸出是計算上不可區分的,則可驗證計算方案VC是隱私的.實驗定義如下.

其中,預言機PProbGen(x)表示調用ProbGen(sk,x)生成(σx,τx),且僅返回表示敵手A的 PProbGen查詢.

定義3(隱私性).為可驗證計算方案VC定義敵手A,其在上述實驗中的優勢為

若對任意的f∈F和任意的概率多項式時間敵手可以忽略不計是成立的,則可驗證計算VC是隱私的.

在外包函數f的每次計算過程中,客戶端執行的算法ProbGen和Verify共同復雜度要比函數f的復雜度要小,其中未考慮復雜度為poly(|f|)的算法KeyGen.原因是由于考慮的是攤銷復雜度模式,即為了提高在線階段效率,客戶端需在離線階段付出大量的計算開銷(和函數f的復雜度相同).

定義4(效率).?x∈Domain(f),?f∈F,其中,F是一個函數族,若算法ProbGen和算法Verify共同運行時間是o(T),其中,T是計算函數f所需時間,則可驗證計算方案VC是有效率的.

2.2 BHHO加密算法

BHHO加密算法是一個基于DDH假設的公鑰加密算法[24].定義q是群G的階,g是群G的生成元,?=「3logq.該公鑰加密算法PKE由以下3種算法組成.

·Gen(1).從群G和{0,1}?中分別一致隨機選擇向量(g1,...,g?)和比特串s=(s1,...,s?),計算h=、密鑰sk=s、公鑰.

·Enc(pk,m).隨機選擇r←Zq.群元素m∈G加密后的密文形式為.

·Dec(sk,c).密文.算法輸出.

BHHO 算法的密鑰和明文都具有加同態性質.定義f(x)=Ax+b為從到的可轉置映射轉換(invertible affine transformation,簡稱 IAT).若M-1(x?|1)?=(f(x)?|1)?,則定義M為f(x)的逆映射轉換(reverse affine transformation,簡稱 RAT).若給定 BHHO公鑰pk和密鑰sk,加密比特p的密文為,則設密鑰sk′=f(sk)∈是0-1向量,那么pk·M是sk′的公鑰,c·M是關于pk·M同樣比特p的密文.明文具有同樣的同態性質.對于密鑰同態,因為在計算過程中用到了轉置運算,所以映射轉換必須是可轉置的.而對于明文同態,任意的映射轉換都可以.

2.3 混淆電路

本節介紹混淆電路的構造,采用 Yao原有構造方法[13,14,19]的表達方式.在半誠實模式下的安全兩方計算中,有一對參與方 Alice和 Bob有各自的輸入,組合使用混淆電路和不經意傳輸可實現安全計算函數.與此不同的是,在可驗證計算中,只有客戶端有私有的輸入.

設有一系列具有n-bit輸入的布爾電路{Cn}n∈N,對于電路C∈{Cn}n∈N中電線w,客戶端隨機選擇兩個?-bit標簽,分別表示電線w的輸入比特為0和1,其中,?是BHHO的密鑰長度.給定輸入電線分別是a和b,輸出電線為c的門電路g,為其隨機選擇4個新2?-bit的掩碼(mask)δi,j,其中i,j∈{0,1},計算如下4個密文對:

其中,操作符*表示門電路的相應操作.客戶端使用 BHHO密鑰加密掩碼δi,j,使用另一個 BHHO密鑰加密經過與掩碼異或的標簽(與?-bit 0連接).4個密文對隨機排序以混淆電路結構.密鑰(也就是電線標簽)由客戶端秘密存放.在電路計算過程中,客戶端將整個混淆電路Γ和輸入電線的標簽(也就是客戶端輸入x∈{0,1}n相應的編碼c)發送給服務器,服務器逐門電路檢查電路,對于門電路g,服務器獲知兩根輸入電線標簽La和Lb,用La解密每個密文對的前半部分,用Lb解密其后半部分,并異或它們,如得到形式,就取其前半部分Lc作為門電路輸出.最后,服務器計算所有的電路輸出電線標簽并發送給客戶端.

定義5(混淆電路).{Cn}n∈N表示一系列具有n-bit輸入的布爾電路,電路的混淆電路方案Gb由以下3個過程組成.

·Gb.Garble(1,C)→(Γ,gsk):獲取電路C,輸出混淆電路Γ和密鑰gsk.

·Gb.Enc(gsk,c)→c:獲取輸入x和密鑰gsk,輸出編碼c.

·Gb.Eval(Γ,c)→y:獲取混淆電路Γ和c,計算輸出y.

定義6(混淆電路的正確性).對每個安全參數,,所有的x∈{0,1}n:

定義7(靜態安全).混淆電路是靜態安全的,如果存在PPT模擬器S,對任意PPT敵手A:

1.挑戰者隨機選擇比特b.

2.敵手A向挑戰者提交C和x.

“三嚴三實”專題教育要求突出問題導向，著力解決一部分領導干部中存在的理想信念動搖、信仰迷茫、精神迷失，宗旨意識淡薄、忽視群眾利益、漠視群眾疾苦，黨性修養缺失、不講黨的原則等問題；著力解決一部分領導干部中濫用權力、設租尋租，官商勾結、利益輸送，不直面問題、不負責任、不敢擔當，頂風違紀還在搞“四風”(即形式主義、官僚主義、享樂主義、奢靡之風)，不收斂不收手等問題；著力解決一部分領導干部中無視黨的政治紀律和政治規矩，對黨不忠誠、做人不老實，陽奉陰違、自行其是，心中無黨紀、眼里無國法等問題。

3.如果b=0,則挑戰者生成和,返回和.

4.如果b=1,則挑戰者生成和,其中,T(C)揭露C的拓撲結構,返回和.

5.最后,敵手A輸出猜測比特b′,如果b′=b,則敵手A獲勝.

定義8(適應性安全).混淆電路是適應性安全的,如果存在PPT模擬器S,則對任意PPT敵手A:

1.挑戰者隨機選擇比特b.

2.敵手A向挑戰者提交C,挑戰者返回.如果b=0,則挑戰者生成;如果b=1,則挑戰者生成,其中,T(C)揭露C的拓撲結構.

4.最后,敵手A輸出猜測比特b′,如果b′=b,則敵手A獲勝.

2.4 可重隨機化的混淆電路

Gentry等人為實現”i-hop”同態加密方案,構造了基于DDH假設的可重隨機化的混淆電路[19,20],利用BHHO的同態性質實現電路的重隨機化,將密鑰和明文看作向量,它們是關于Zq任意映射函數的同態(我們定義映射函數為與置換矩陣(permutation matrix)相乘).通過兩個隨機置換π,π′,可將密文EncL(L′)轉換成.對于輸入電線分別是a和b、輸出電線為c的門電路g,等式(1)定義了它的4個密文對.RATπa,πb,πc分別是與a,b,c相對應的[?+1]上的隨機比特序列,采用BHHO密鑰同態和明文同態性質將等式(1)的4個密文對轉換為

定義9(可重隨機化的混淆電路).是[?+1]上的隨機比特序列 RAT,混淆電路Γ的可重隨機化混淆電路方案由如下3個過程組成:reRandGb={reRandGb.Gate,reRandGb.InLabel,reRandGb.OutLabel}.

3 技術概述

文獻[19]中構造了基于BHHO加密算法(詳見第2.2節)的可重隨機化混淆電路.在本文中,需要服務器利用BHHO算法的同態性質和可重隨機化性安全重復重隨機化來自客戶端的混淆電路.具體來說,給定輸入電線分別是a和b,輸出電線為c的門電路g(用4個密文對表示),客戶端選擇3個與電線a,b,c分別對應的RATπa,πb,πc,以及4個隨機掩碼,其中,i,j∈{0,1},將它們發送給服務器(我們定義RAT為與一個置換矩陣的乘積運算,IAT也類似).接下來,服務器將每個密文對的前半部分與πa,πb分別相乘,后半部分與πb,πc分別相乘,并且將 4個掩碼與此時的4個密文對分別做異或運算.但是,服務器直接使用RATπa,πb,πc重隨機化門電路會導致混淆電路重用變得不再安全.重隨機化標簽的方法是從混淆電路的電線標簽L和其IATπ′入手,將π′應用于L,也就是π′(L),而π′又可以從隨機的 RAT獲得.于是,服務器在逐個門電路檢查重隨機化電路時,就能從π′和π′(L)中提取標簽L.在環安全中,模擬器已知RAT但不知重隨機化的密鑰[24].

我們的想法是限制服務器明確地獲知RAT或 IAT,解決方案是使用數學隱藏方法[21]和 Kilian的隨機化技術[22].數學隱藏方法可將每個RAT表達為3個矩陣的乘法鏈,Kilian的隨機化技術可將其中的每個矩陣前乘和后乘可轉置隨機矩陣.例如,設某個RAT為可轉置隨機矩陣A,表示為3個矩陣B,C,D乘法鏈,選取可轉置隨機矩陣R1,R2,將3個矩陣分別表示為隨機化形式:,其中,R0是單位矩陣,它們相乘即可恢復矩陣A.

客戶端的隨機化密鑰生成算法 KeyGen為混淆電路的門電路i一致選取可轉置隨機矩陣,為混淆電路隨機選取隨機矩陣,且構建矩陣(由服務器為門電路選取掩碼對電路的安全性沒有影響).接下來,在每次外包計算中,客戶端的問題生成算法 ProbGen也為混淆電路選取可轉置隨機矩陣,構造 3個矩陣,其中,R0是大小合適的單位矩陣.接下來,服務器執行算法 Compute為門電路i計算矩陣鏈乘:

其中,P分別是門電路i的兩個輸入電路和輸出電線的被用于隨機化門電路i,上述過程并沒有將RAT泄露給服務器.重隨機化前后的門電路如圖1所示,重隨機化多個門電路如圖2所示.這時,門電路1的輸出電線是門電路2的輸入電線之一,它們具有一致的重隨機化狀態和同樣的RAT.

Fig.1 A gate that will be re-randomized and the re-randomized gate圖1 重隨機化前的門電路和重隨機化后的門電路

Fig.2 Two gates that will be re-randomized and the re-randomized gates圖2 重隨機化多個門電路前后狀態

給定電路輸入電線的IAT(從RATP4Pi,1P5和P4Pi,2P5易得),客戶端的問題生成算法ProbGen利用BHHO加密算法的密鑰同態重隨機化輸入標簽.根據這些重隨機化標簽和重隨機化電路,服務器利用Compute算法逐門電路檢查重隨機化電路,得到中間以及電路輸出門電路由IAT隨機化的標簽.

輸出的正確性要求服務器將正確輸出交付給客戶端,若根本什么都沒有交付,則服務器被認為是欺騙或計算錯誤.Gennaro等人指出,如果通過檢查重隨機化混淆電路恢復出正確的電路輸出電線標簽,則足夠表明服務器的電路重隨機化過程是誠實的(可參考第 2.3節)[3].另外,我們的方案還能容忍服務器發起任意次數的驗證查詢.也就是說,服務器能夠獲知客戶端是否接受或拒絕計算結果.在驗證查詢下安全的原因是,客戶端接受或拒絕決定的比特只與混淆電路的重隨機化過程計算相關.

4 可驗證計算協議

4.1 協議形式化描述

高層次上的協議描述如下所述.

· 在離線階段,客戶端將函數的混淆電路形式和所有門電路的矩陣(Kilian的隨機化技術隱藏的映射轉換固定部分)發送給服務器.

可驗證計算協議構造如下所示.

·KeyGen(1,f)→(pk,sk).將f表示為電路C.該算法由客戶端執行如下步驟.

? 首先,運行混淆電路生成算法產生電路C的混淆電路,混淆電路電線i標簽記為.具體來說,執行,其中,Γ為混淆電路,是電路輸入電線標簽,是電路輸出電線標簽.對于門電路i,j∈[|Γ|],隨機選擇可逆矩陣和4個門電路隨機掩碼,為混淆電路也隨機選擇可逆矩陣:

·ProbGen(sk,x)→(σx,τx).定義輸入x為n比特大小,即x=x1,…,xn.為混淆電路隨機選擇可逆矩陣P4,P5∈,構造矩陣,其中,R0是大小合適的單位矩陣.執行,生成輸入編碼c.對輸入標簽i∈[n],計算:

其中,b∈{1,2},γi(ci)表示重隨機化輸入標簽.電路輸出電線的 IATη1,…,ηn也可通過類似計算得到.

·Compute(pk,σx)→(σy).解析σx,對每個i∈[|Γ|],計算,并選擇4個隨機掩碼.運行.計算,.輸出σy=(e1,…,en).

·Verify(sk,σy,τx)→(acc,y).解析σy為e1,…,en.如果對輸出標簽i∈[n],等式Li=reRandGb.OutLabel(ηi,ei)成立,則acc=1(接收);否則,acc=0(拒絕).如果acc=1,則利用密鑰sk將ei映射為輸出y;否則,輸出⊥.

協議的正確性可由混淆電路、可重隨機化的混淆電路,數學偽裝方法和Kilian的隨機化技術的正確性直接得出.BHHO加密算法確保了輸入和輸出隱私,而隨機矩陣鏈乘使得映射轉換也是隱私的,對服務器隱藏的原混淆電路可實現輸入和輸出隱私的電路重用(見定理2).協議的離線階段(執行KeyGen)代價為O(poly()|C|),與函數f相關而與被委托輸入無關,其中,|C|是函數f電路的大小.每次外包計算中,客戶端外包計算在線的代價是O(poly()·n)(執行 ProbGen),計算 3 個矩陣鏈乘代價是O(1),執行 Verify 的代價是O(poly()·n),因為在線代價與函數f的電路大小無關,所以該方案是非平凡的(non-trivial).也就是說,客戶端自己計算函數f的開支比在線代價要大.服務器在線階段的代價是O(poly()|C|)(執行Compute).

文獻[3]中具有預見性的方案雖然類似于上述可驗證計算協議,但是需要強調與之不同的幾點.

· Gennaro等人給出的可驗證計算方案只在敵手不能對客戶端發起任何數量的驗證查詢這種較弱的模型下被證明是安全的.我們的方案能夠容忍多項式次數的惡意驗證查詢.

· Gennaro等人組合使用Yao的混淆電路和FHE實現安全的多項式次數輸入的混淆電路重用,輸入比特相應的標簽使用FHE加密.為實現多項式次數輸入的混淆電路重用,我們使用BHHO加密算法的加同態性質重隨機化標簽和混淆電路.

· Gennaro等人僅考慮客戶端將任意函數計算外包給不被信任的服務器這種非交互可驗證計算模式,我們不僅考慮可驗證計算,而且也考慮了兩方計算下的私有函數計算(private function evaluation,簡稱PFE)協議(詳見第5節).

· 我們的方案是基于DDH假設,比Gennaro等的方案速度更快、更加緊湊.

4.2 安全分析

利用數學偽裝方法可阻止服務器使用已用過的 RAT重隨機化混淆電路,但不包括那些與電路輸入電線和電路輸出電線相關的RAT.舉例來說,設門電路i的RAT分別是(不采用數學偽裝方法,因此,此時RAT是一個矩陣,而不再是 3個矩陣的乘法鏈),在每次外包計算中,客戶端構造和并發送給服務器,其中,R0是單位矩陣,R1是隨機置換矩陣(注意,這里僅使用 Kilian的隨機化技術).此時,服務器就可計算,其中,表示已用于之前外包計算矩陣.另一方面,此時客戶端開銷與電路的大小具有相同的階,這樣,客戶端可僅發送一個新的電路給服務器,實現上這樣更容易.

同樣地,利用 Kilian的隨機化技術隨機隱藏 RAT的每個部分,限制敵手以基本元素的方式操縱密文組件,比如不按序計算矩陣乘積.敵手有兩類可能的攻擊Kilian的隨機化技術方法[25].

· 一類攻擊方法是混合輸入攻擊,敵手正確計算矩陣鏈乘,但是不遵循矩陣鏈乘的結構.簡而言之,和都前乘和后乘相同的矩陣,服務器可用代替計算矩陣鏈乘Zi,1,或者用代替計算矩陣鏈乘Zi,2.但是,給定電路輸入電線的重隨機化標簽,服務器在逐個門電路檢查重隨機化電路時,并不能得到電路輸出電線的正確重隨化標簽[13].

· 另一類攻擊方法是部分計算攻擊,敵手計算客戶端不同輸入下的部分矩陣鏈乘,試圖通過比較這些中間值了解RAT的一些信息.例如,服務器在2個不同客戶端輸入下分別計算矩陣鏈乘Zi,1的前兩個矩陣乘積,也就是,如果上述Kilian矩陣編碼方案是理想的,則使用部分計算攻擊的敵手并不能獲得任何有用信息.

定理1.若DDH假設是存在的,則上述非交互可驗證計算協議對外包函數f是安全的.

證明:接下來,采用模擬證明技術(simulation proof technique)[13,26]證明定理1成立.首先,先給出引理1和引理2及其證明.

引理 1.如果函數f是多項式時間可計算函數,由Garble(1,C)生成混淆電路的分布和由模擬器執行GarbleSim(1,C)生成混淆電路的分布在DDH假設下是計算上不可區分的.

證明:引理1的證明過程類似于Lindell-Pinkas關于Yao協議的證明過程[13].

首先描述模擬器的構造.模擬器執行GarbleSim(1,C),生成一個偽造的混淆電路,過程如下所述:對于混淆電路的每個門電路g,設其輸入電線分別是a和b,輸出電線為c;為電線a分別選擇活動標簽(active label)La和不活動標簽(inactive label)La′,如果標簽被用于計算混淆電路則稱它是活動標簽,同一電線的另一標簽就是不活動標簽.同樣地,為電線b分別選擇活動標簽和不活動標簽Lb,La′,為電線c選擇活動標簽和不活動標簽Lc,Lc′.為該門電路隨機選擇 4個新 2?-bit掩碼δ1,δ2,δ3,δ4,計算并隨機排序如下 4個密文對:

其中,所有密文對只加密輸出電線的活動標簽.上述所有的門電路構成了GarbleSim(1,C)生成的混淆電路.

為了證明模擬器產生混淆電路的分布與實際執行Garble(1,C)生成混淆電路的分布是計算上不可區分的,接下來使用標準的混合體論證(hybrid argument)[26],需定義一系列的混合體H0,H1,...,H|Γ|.

·H0:此混合體實際執行Garble(1,C)生成混淆電路Γ.

·Hi,其中,i∈(0,|Γ|):此混合體與H0的區別在于前i個門電路g1,...,gi的 4個密文對是由門電路輸入標簽所有4個組合加密門電路輸出電線活動標簽的密文組成,其他門電路與H0的混淆電路門電路相同.

·H|Γ|:此混合體執行GarbleSim(1,C)生成混淆電路,每個門電路都只有輸出電線的活動標簽加密.

對于所有i∈[1,|Γ|],任意兩個連續的混合體Hi-1和Hi的區別在于:Hi-1中門電路gi輸出電線不活動標簽的密文在Hi中被輸出電線活動標簽的密文所取代.

假設門電路gi的輸入電線分別是a和b,輸出電線為c.電線分別是a活動標簽和不活標簽分別是,相類似電線b的分別是電線c的分別是中該門電路的4個密文對如下:

Hi-1和Hi是計算上不可區分的,這可通過歸約到BHHO加密算法的語義安全得出.

假設存在PPT區分器D和多項式p(·),對無限多的n有:

利用區分器D構造PPT敵手A,A接收門電路gi密文對并構造混淆電路,該電路一部分是Garble(1,C)真實產生的門電路,另一部分是GarbleSim(1,C)偽造產生的門電路.若A接收的門電路gi密文對與Hi-1中的門電路gi密文對相同,則該構造與Hi-1的混淆電路一致;若A接收的門電路gi密文對與Hi中的門電路gi密文對相同,則該構造與Hi的混淆電路一致.如果敵手A能夠區分Hi-1和Hi,就可以區分其中門電路gi的密文對,這與 BHHO加密算法的安全性相矛盾. □

引理2.有效算法reRandGb輸入為隨機數r和Garble′(1,C)生成的混淆電路Γ′,輸出電路C的重隨機化混淆電路,則Garble(1,C)生成混淆電路Γ的分布和重隨機化混淆電路的分布在DDH假設下是計算上不可區分的.

證明:引理 2的證明方法與引理 1的類似.為了證明以上兩個分布是不可區分的,定義一系列的混合體H0,H1,...,H|T|,這里的T表示混淆電路的電線數量.

·H0.此混合體執行Gb.Garble(1,C)生成混淆電路Γ,使其輸出與執行Gb.Garble′(1,C)生成的混淆電路Γ′輸出相同,則混淆電路Γ的分布與混淆電路Γ′的分布是一致的.

·Hi,其中,i∈(0,|T|).此混合體生成的混淆電路前i根電線是由重隨機化混淆電路Γ′的前i根電線得到,其他電線與混淆電路Γ′的電線相同.

·H|T|.此混合體是執行reRandGb生成的重隨機化混淆電路,每根電線都是重隨機化混淆電路Γ′的相應電線而得到的.

對于所有i∈[1,|T|],任意兩個連續的混合體Hi-1和Hi的區別在于第i根電線在Hi-1中與混淆電路Γ′的第i根電線相同,而Hi的第i根電線是由重隨機混淆電路Γ′的第i根電線而得到的.Hi-1和Hi是計算上不可區分的,這可由BHHO加密算法安全性得出. □

接下來,利用引理1和引理2證明定理1在兩方計算下是成立的,那么定理1在可驗證計算下也是成立的(我們考慮的不僅是可驗證計算,還有在兩方計算下的私有函數計算,見第5節).基于模擬的安全強于基于不可區分的安全,如果采用模擬證明技術證明協議是基于模擬的安全,則一定是計算不可區分安全(見定義2).因此,在證明中需構造惡意的服務器和惡意的客戶端,并且模擬服務器的視圖(view)與客戶端的視圖.定義一個模擬器Sim={Simc,Sims},Simc模擬客戶端的視圖,Sims模擬服務器的視圖.

·Simc.給定客戶端的輸入x和計算結果y=f(x),構造模擬客戶端的Simc.首先,一致隨機選擇矩陣;接下來計算矩陣乘積,為了生成混淆電路Γ,執行;然后選擇客戶端輸入x相對應的輸入電線活動標簽;對輸入電線i∈[n],執行reRandGb.InLabelSim(γi,ci)→γi(ci),其中,或.Simc剩下的步驟與客戶端執行過程相同.

·Sims.給定客戶端輸入x和計算結果y=f(x),Sims模擬服務器構造混淆電路,其計算結果等于f(x).具體來說,執行,在中活動標簽與相關聯.考慮輸入電線是a,b和輸出電線為c的門電路,可用如等式(1)的4個密文對表示.然而,此時4個密文對只包含門電路輸出電線的活動標簽密文.Sims剩下的步驟與服務器執行過程相同.

為了證明協議執行過程的模擬器視圖與協議實際執行是計算上不可區分的,需定義一系列的混合體,它們開始于客戶端與服務器協議的真實執行,結束于充當客戶端與服務器角色的模擬器理想執行.

·H0.此混合體中的客戶端和服務器都遵循協議的實際執行(見第4.1節).

·H1.此混合體與H0的區別僅在于的計算方法.模擬器在計算中不采用Kilian的隨機化技術,而是為客戶端和服務器端都選擇隨機矩陣.

·H2.此混合體與H1的區別僅在于Zi,1,Zi,2的計算方法.Simc在計算中不采用數學偽裝方法,而是直接計算.再者,Sims將Zi,1,Zi,2作為輸入,執行,生成重隨機化混淆電路.

·H3.此混合體與H2的區別僅在于由模擬器新構建混淆電路取代重隨機化的混淆電路.具體來說,模擬器模擬客戶端執行Gb.Garble(1,C),生成混淆電路;接下來為客戶端輸入x選取電路輸入電線標簽,執行Gb.Enc(gsk,x),生成輸入的編碼.相類似地,模擬器模擬服務器執行Gb.Garble(1,C),生成混淆電路.

·H4.此混合體與H3的區別僅在于由模擬器執行Gb.GarbleSim(1,C),新構建混淆電路取代原有電路.具體來說,模擬器模擬客戶端執行Gb.GarbleSim(1,C),生成混淆電路;接下來為客戶端輸入x選取電路輸入電線標簽,執行reRandGb.InLabelSim(γi,ci),重隨機化輸入.相類似地,模擬器模擬服務器執行Gb.GarbleSim(1,C),生成混淆電路.

下面證明每個混合體與相鄰的混合體是不可區分的.

引理3.對所有的概率多項式時間敵手.

證明:根據 Kilian的隨機化技術正確性,返回給敵手A的矩陣分布上并沒有變化.因此,敵手A贏得H1的概率仍然與贏得H0的概率相同. □

引理4.對所有的概率多項式時間敵手.

證明:敵手A贏得H1的概率與贏得H2的概率相同,因為否則就存在一個攻擊者對數學偽裝方法具有不可忽略的優勢. □

引理5.對所有的概率多項式時間敵手.

證明:根據引理2的證明可以得出:給定一個由Gb.Garble(1,C)生成的混淆電路以及由reRandGb生成的重隨機化混淆電路,沒有計算能力受限的敵手能夠區分這兩個電路.這意味敵手A在H3中的概率與在H2中的概率相同. □

引理6.對所有的概率多項式時間敵手.

證明:根據引理 1的證明可得出:由Gb.GarbleSim(1,C)得到的電路與由Gb.Garble(1,C)得到的電路,沒有計算能力受限的敵手能夠區分這兩個電路.這意味敵手A在H4中的概率與在H3中的概率相同. □

接下來說明在基于模擬的安全下客戶端不會接受敵手A偽造的計算結果.若敵手A不能使驗證算法接受一個不正確的輸出,則可驗證計算方案是安全的(見定義2關于可驗證計算方案是計算不可區分安全的定義).為了說明客戶端不會接受敵手A偽造的計算結果,需要給定輸入x和計算結果y=f(x),構造客戶端模擬器具體過程如下.

3.敵手A向預言機PVerify發起查詢,預言機返回acc,當且僅當Verify(sk,σx,τx)→(acc,y).預言機 Pverify僅返回接收/拒絕比特acc.

4.步驟2和步驟3可重復多項式次數.

5.給定敵手A的σy,Sim′c生成(acc,y)←Verify(sk,σy,τx).如果σy是偽造的計算結果,Simc′將不能映射出正確的混淆電路輸出標簽,則acc=0(拒絕),輸出⊥;否則,acc=1(接收),并輸出y.

綜上所述,定理1得證. □

定理2.若DDH假設是存在的,則上述非交互可驗證計算協議對服務器是隱私的.

證明:該證明與定理1的證明都具有類似形式的混合體和證明過程.服務器的隱私性可由RAT的隱私、可重隨機化的混淆電路安全性和Yao的混淆電路安全性得出. □

4.3 適應性安全

靜態安全的混淆電路是指輸入不依賴于混淆電路[13,27](見定義7).與之相反,適應性安全的混淆電路是指,如果敵手在查看混淆電路以后還允許適應性地選擇輸入,此時混淆電路仍是安全的(見定義8).Yao的混淆電路只能做到靜態安全的,這是因為為了提高在線階段的效率,混淆電路的生成和發送通常都在離線階段,惡意的敵手就有可能根據混淆電路自己選擇輸入,使得混淆電路不再安全.文獻[3]的可驗證計算方案使用了 Yao的混淆電路,為了保證方案的安全,必須在發送混淆電路之前確定輸入,因此該方案是靜態安全的.

第4.1節的可驗證計算協議雖然也是靜態安全的,但可采用兩種方法實現適應性安全:一種方法是將該協議運用復雜性杠桿(complexity leveraging)實現適應性安全;另一種方法是將該協議作細微的調整,即可做到適應性安全.為了使惡意的敵手在離線階段不能根據混淆電路自己選擇輸入,客戶端只需將所有門電路的密文對的前半部分和后半部分別與一個大小合適的隨機可逆矩陣相乘.相應的,構造矩陣修改為,計算,再將現在的Zi,1,Zi,2用于隨機化門電路i.上述過程既沒有將 RAT泄露給敵手,也保證敵手不能嘗試混淆電路的輸入,即實現了適應性安全.為了說明這一點,可采用文獻[27]中靜態安全轉換為適應性安全的構造方法.具體來說,因為定理1成立,故存在靜態安全 PPT模擬器S,對任意PPT敵手A(見定義7),

給定任意適應性安全PPT敵手A1,構建靜態安全敵手A.若由模擬器S能夠構建適應性安全PPT模擬器S1:

則適應性安全成立(見定義8).

1.挑戰者隨機選擇比特b1.

2.敵手A1向挑戰者提交C,挑戰者返回..如果b1=0,挑戰者返回隨機混淆電路;如果b1=1,挑戰者也返回隨機混淆電路.

3.敵手A1向挑戰者提交x.

4.如果b1=0,則挑戰者調用定義7的步驟3,生成,并將所有門電路的密文對的前半部分和后半部分別與相乘生成,并返回和.

5.如果b1=1,則挑戰者調用定義7的步驟4,生成和,并將所有門電路的密文對的前半部分和后半部分別與相乘生成,并返回和.

6.最后,敵手A1輸出猜測比特,如果,敵手A1獲勝.

設b是定義7的挑戰比特,從上述適應性安全實驗可以得出:

所以,等式(3)成立.

5 可重用的密碼轉置防火墻

接下來,將第 4.1節的協議應用于密碼轉置防火墻[23],從而提供一種密碼轉置防火墻的新模式,即可重用的密碼轉置防火墻.密碼轉置防火墻聚焦于用戶與外部通訊的密碼安全,可解釋為一個狀態算法,應用于用戶發送和接收已由某些密碼算法處理的消息.兩方計算下的私有函數計算PFE協議有一對參與方分別是Alic和Bob,Alice擁有私有的函數f,Bob擁有私有的輸入x,雙方計算f(x)并保證輸入x和函數f的隱私性和結果的正確性.PFE協議的密碼轉置防火墻主要技術工具是可重隨機化的不經意傳輸和可重隨機化的混淆電路.Bob(Bob的密碼轉置防火墻)和Alice(Alice的密碼轉置防火墻)執行可重隨機化的不經意傳輸,Alice向Bob透露電路輸入電線的兩個重隨機化標簽其中之一,而不了解確切是哪一個.接下來,Alice的密碼轉置防火墻將重隨機化的混淆電路發送給Bob,Bob就可以根據重隨機化標簽計算電路.然而,Alice的密碼轉置防火墻重用用于重隨機化電路的Yao的混淆電路是不安全的,這是因為重復的重隨機化等同于混淆電路的重用.所以,我們提出一種可重用的密碼轉置防火墻,用戶一次生成混淆電路,接下來,密碼轉置防火墻可安全地重隨機化多次.

5.1 不經意傳輸

Naor-Pinks/Aiello-Ishai-Reingold證明了不經意傳輸協議可在誠實但好奇模式下是安全的[28,29].不經意傳輸協議有兩個參與方:發送方Alice和接收方Bob.Alice的輸入為a0,a1∈{0,1};Bob的輸入是選擇的比特b∈{0,1}.Alice和Bob之間協議實現如圖3所示,其中,G是階為q的群.

Fig.3 Oblivious transfer(OT)protocol圖3 不經意傳輸協議OT

定義10(可重隨機化的不經意傳輸).如圖3所示兩消息的不經意傳輸協議,設msg1=(g,h,x,y0,y1)是第1輪的消息,msg2=(u0,v0,u1,v1)是第2輪的消息.

不經意傳輸協議是可重隨機化的,若存在輸入為msg1,msg2和隨機數r的有效算法reRandOT,即使給定r,b,a0,a1,msg1,msg2,以下兩個分布是計算上不可區分的.

5.2 私有函數計算的可重用密碼轉置防火墻

Alice的PFE可重用密碼轉置防火墻WA的構造與可驗證計算協議的構造非常類似,技術上的區別在于,WA需要定義如何構造不經意傳輸的重隨機化.因為Bob的可重用密碼轉置防火墻WB與文獻[23]的不經意傳輸協議重隨機化是一致的,故此處省略.構造Alice的PFE可重用轉置密碼防火墻如圖4所示.本質上該構造與可驗證計算協議相同,安全要求相同,證明也類似.

定理3.若DDH假設成立,如圖4所示的Alice的可重用密碼轉置防火墻對于函數f是正確的和安全的.

證明:Alice的可重用密碼轉置防火墻的正確性證明如下.

G是素數階q的循環群,定義是Bob發送給Alice的初始消息,Bob的防火墻安全性可直接由DDH假設得出.惡意模式下的可重隨機化不經意傳輸安全和可重隨機化混淆電路安全確保Alice的防火墻是安全的.接下來證明可重隨機化不經意傳輸的安全性.

Fig.4 Alice’s reusable cryptographic rerverse firewall for the private function evaluation protocol圖4 私有函數計算協議中Alice的可重用密碼轉置防火墻

WB·(WA·Alice)對來自 Bob的任意有效消息(g,h,x,y0,y1)以不可忽略的概率做出一致隨機有效響應.若,則是一致隨機群元素.為了說明這一點,需要利用等式(或者).若(或),的分布是一致和獨立的.

1.輸入比特σ,SimA產生.

2.隨機選擇(a0,a1)←{0,1}和.

SimA的輸出與在真實協議中Bob接收來自 Alice的可重用密碼防火墻的消息是不可區分的,這可從 DDH假設得出. □