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

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

2(南京大學(xué) 計算機(jī)科學(xué)與技術(shù)系,江蘇 南京 210023)

3(福州大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院,福建 福州 350117)

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

5(南京農(nóng)業(yè)大學(xué) 信息科技學(xué)院,江蘇 南京 210095)

1 引 言

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

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

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

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

1.1 本文貢獻(xiàn)

在本文中,我們將首先構(gòu)造一個采用加同態(tài)加密的非交互可驗證計算協(xié)議.它是基于 DDH假設(shè),在任意新輸入下能夠?qū)崿F(xiàn)客戶端基于混淆電路的外包計算,可以容忍多項式次數(shù)的惡意驗證查詢,并為提供客戶端的輸入輸出隱私保護(hù),以及函數(shù)計算的正確性和語義的安全性.

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

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

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

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

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

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

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

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

2 預(yù)備知識

2.1 可驗證計算定義

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

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

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

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

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

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

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

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

考慮關(guān)于敵對的服務(wù)器A的如下實驗.

其中,預(yù)言機(jī)PVerify(σ,τ)返回acc,當(dāng)且僅當(dāng)表示敵手A的 PVerify 查詢.

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

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

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

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

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

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

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

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

2.2 BHHO加密算法

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

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

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

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

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

2.3 混淆電路

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

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

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

定義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(混淆電路的正確性).對每個安全參數(shù),,所有的x∈{0,1}n:

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

1.挑戰(zhàn)者隨機(jī)選擇比特b.

2.敵手A向挑戰(zhàn)者提交C和x.

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

3.如果b=0,則挑戰(zhàn)者生成和,返回和.

4.如果b=1,則挑戰(zhàn)者生成和,其中,T(C)揭露C的拓?fù)浣Y(jié)構(gòu),返回和.

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

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

1.挑戰(zhàn)者隨機(jī)選擇比特b.

2.敵手A向挑戰(zhàn)者提交C,挑戰(zhàn)者返回.如果b=0,則挑戰(zhàn)者生成;如果b=1,則挑戰(zhàn)者生成,其中,T(C)揭露C的拓?fù)浣Y(jié)構(gòu).

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

2.4 可重隨機(jī)化的混淆電路

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

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

3 技術(shù)概述

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

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

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

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

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

Fig.2 Two gates that will be re-randomized and the re-randomized gates圖2 重隨機(jī)化多個門電路前后狀態(tài)

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

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

4 可驗證計算協(xié)議

4.1 協(xié)議形式化描述

高層次上的協(xié)議描述如下所述.

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

可驗證計算協(xié)議構(gòu)造如下所示.

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

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

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

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

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

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

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

文獻(xiàn)[3]中具有預(yù)見性的方案雖然類似于上述可驗證計算協(xié)議,但是需要強(qiáng)調(diào)與之不同的幾點.

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

· Gennaro等人組合使用Yao的混淆電路和FHE實現(xiàn)安全的多項式次數(shù)輸入的混淆電路重用,輸入比特相應(yīng)的標(biāo)簽使用FHE加密.為實現(xiàn)多項式次數(shù)輸入的混淆電路重用,我們使用BHHO加密算法的加同態(tài)性質(zhì)重隨機(jī)化標(biāo)簽和混淆電路.

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

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

4.2 安全分析

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

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

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

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

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

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

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

證明:引理1的證明過程類似于Lindell-Pinkas關(guān)于Yao協(xié)議的證明過程[13].

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

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

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

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

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

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

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

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

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

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

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

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

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

·H0.此混合體執(zhí)行Gb.Garble(1,C)生成混淆電路Γ,使其輸出與執(zhí)行Gb.Garble′(1,C)生成的混淆電路?！漭敵鱿嗤?則混淆電路Γ的分布與混淆電路Γ′的分布是一致的.

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

·H|T|.此混合體是執(zhí)行reRandGb生成的重隨機(jī)化混淆電路,每根電線都是重隨機(jī)化混淆電路?！涞南鄳?yīng)電線而得到的.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.步驟2和步驟3可重復(fù)多項式次數(shù).

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

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

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

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

4.3 適應(yīng)性安全

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

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

給定任意適應(yīng)性安全PPT敵手A1,構(gòu)建靜態(tài)安全敵手A.若由模擬器S能夠構(gòu)建適應(yīng)性安全PPT模擬器S1:

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

1.挑戰(zhàn)者隨機(jī)選擇比特b1.

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

3.敵手A1向挑戰(zhàn)者提交x.

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

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

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

設(shè)b是定義7的挑戰(zhàn)比特,從上述適應(yīng)性安全實驗可以得出:

所以,等式(3)成立.

5 可重用的密碼轉(zhuǎn)置防火墻

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

5.1 不經(jīng)意傳輸

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

Fig.3 Oblivious transfer(OT)protocol圖3 不經(jīng)意傳輸協(xié)議OT

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

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

5.2 私有函數(shù)計算的可重用密碼轉(zhuǎn)置防火墻

Alice的PFE可重用密碼轉(zhuǎn)置防火墻WA的構(gòu)造與可驗證計算協(xié)議的構(gòu)造非常類似,技術(shù)上的區(qū)別在于,WA需要定義如何構(gòu)造不經(jīng)意傳輸?shù)闹仉S機(jī)化.因為Bob的可重用密碼轉(zhuǎn)置防火墻WB與文獻(xiàn)[23]的不經(jīng)意傳輸協(xié)議重隨機(jī)化是一致的,故此處省略.構(gòu)造Alice的PFE可重用轉(zhuǎn)置密碼防火墻如圖4所示.本質(zhì)上該構(gòu)造與可驗證計算協(xié)議相同,安全要求相同,證明也類似.

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

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

G是素數(shù)階q的循環(huán)群,定義是Bob發(fā)送給Alice的初始消息,Bob的防火墻安全性可直接由DDH假設(shè)得出.惡意模式下的可重隨機(jī)化不經(jīng)意傳輸安全和可重隨機(jī)化混淆電路安全確保Alice的防火墻是安全的.接下來證明可重隨機(jī)化不經(jīng)意傳輸?shù)陌踩?

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

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

1.輸入比特σ,SimA產(chǎn)生.

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

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