可復(fù)用Garbling 的效率分析及簡化方案*

胡予濮, 劉 君, 王保倉

西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論與關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室, 西安 710071

1 前言

早期的garbling 方案(我們稱之為簡單garbling 方案) 可以歸結(jié)為兩類: Bellare 等人在2012 年提出的garbling (下文簡稱為BHR12 garbling) 方案[9]和Ishai 等人在2000 年提出的(下文簡稱為IK00 garbling) 方案[10].

BHR12 garbling 方案是暴露原電路的拓?fù)浣Y(jié)構(gòu), 僅僅隱藏輸入值和原電路的每一步運(yùn)算符號. 這一特點(diǎn)使得BHR12 方案非常簡潔, 但同時使得BHR12 方案不可復(fù)用, 即對于同一個原電路C和多個不同的輸入值x, 其計(jì)算需要多個不同的{x,C}編碼方式. 換句話說, 對于同一個原電路C和多個不同的輸入值x, 如果使用相同的編碼方式, 就會逐漸暴露原電路的各步運(yùn)算符號, 乃至暴露原電路.

IK00 garbling 方案是使用一種分支程序, 增加輸出維數(shù), 降低每個輸出分量函數(shù)的次數(shù). 每個輸出分量函數(shù)僅為輸入值和隨機(jī)值的3 次函數(shù); 當(dāng)隨機(jī)值被確定后, 每個輸出分量函數(shù)僅為輸入值的1 次函數(shù).IK00 方案的尺寸龐大, 遠(yuǎn)遠(yuǎn)大于原電路的尺寸, 而且不能保證IK00 方案的尺寸是多項(xiàng)式尺寸. IK00 方案不僅隱藏輸入值和原電路的每一步運(yùn)算符號, 也似乎隱藏了原電路的拓?fù)浣Y(jié)構(gòu), 因此IK00 方案具有升級為obfuscation 的趨勢, 但這種隱藏難以分析.

后期的garbling 方案(我們稱之為復(fù)雜garbling 方案) 集中在可復(fù)用的garbling, 使用全同態(tài)加密、密鑰全同態(tài)加密、屬性加密、函數(shù)加密等技術(shù), 將不可復(fù)用的garbling 方案改造成可復(fù)用的garbling 方案[5,6]. 其中, Goldwasser 等人在2013 年構(gòu)造了第一個可復(fù)用garbling (下文簡稱為GKP+13 可復(fù)用garbling) 方案[5].

本文論述經(jīng)典GKP+13 可復(fù)用garbling 方案的效率和簡化方案, 具體如下.

· 本文指出, GKP+13 可復(fù)用garbling 方案不但尺寸龐大, 而且其內(nèi)部結(jié)構(gòu)含有一個一次性的(即不可復(fù)用的)garbling. 換句話說, GKP+13 可復(fù)用garbling 方案實(shí)際上是不可復(fù)用的.

· 本文給出一種簡化方案, 將底層的全同態(tài)加密部件從變動密鑰簡化為固定密鑰, 其安全性沒有任何損失. 簡化方案消減了方案的尺寸, 雖然簡化方案實(shí)際上仍然是不可復(fù)用的garbling 方案.

本文內(nèi)容編排如下. 第2節(jié)是預(yù)備知識, 回顧布爾電路的一般表達(dá)式, 以及早期的BHR12 garbling 方案和IK00 garbling 方案. 第3節(jié)給出GKP+13 可復(fù)用garbling 方案. 第4節(jié)給出我們的分析和簡化方案.

2 預(yù)備知識

2.1 布爾電路的一般表達(dá)式

多項(xiàng)式時間可計(jì)算的布爾函數(shù)一般并不適合用代數(shù)正規(guī)型來表示, 因?yàn)轫?xiàng)的個數(shù)很可能是指數(shù)多個.最合理的表達(dá)式是按照運(yùn)算順序來表示每一步的{兩個輸入比特, 運(yùn)算符號, 一個輸出比特}. 設(shè)運(yùn)算符號集為{+,×}, 其中‘‘+” 為異或, ‘‘×” 為乘積. 則n維布爾函數(shù)C(x) 的一般表達(dá)式如下.

· 輸入:x=(x1,x2,··· ,xn),xn+1. 其中xn+1=1 為常數(shù).

· 對于i=n+ 2,n+ 3,··· ,N, 令xi ←xa(i)Oixb(i). 其中a(i)∈{1,2,··· ,i- 1},b(i)∈{1,2,··· ,i-1},a(i)＜b(i),Oi ∈{+,×}.

· 輸出:xN. 其中xN=C(x).

我們稱{(x1,x2,··· ,xn),xn+1;(xi,a(i),b(i),Oi),i=n+2,n+3,··· ,N}為n維布爾函數(shù)C(x) 的一般表達(dá)式, 稱N為C(x) 的電路尺寸, 稱{(a(i),b(i)),i=n+2,n+3,··· ,N}為C(x) 的電路拓?fù)浣Y(jié)構(gòu), 稱{Oi,i=n+2,n+3,··· ,N}為C(x) 的電路運(yùn)算符號序列.

2.2 BHR12 garbling 方案[9]

Alice 取兩個公開的概率分布X0和X1, 這兩個概率分布能夠完全區(qū)分. Alice 取一個公開的對稱加密算法E(·,·), 其中的兩個位置依次為明文位置和密鑰位置. 對于每個i= 1,2,··· ,N-1, Alice 隨機(jī)選取一個j ∈{0,1}, 然后定義Xi,0=Xj,Xi,1=X1-j. Alice 定義XN,0=X0,XN,1=X1.

2.3 IK00 garbling 方案[10] 的第一步: 分支程序

設(shè)n維布爾函數(shù)C(x) 的一般表達(dá)式為{(x1,x2,··· ,xn),xn+1;(xi,a(i),b(i),Oi),i=n+ 2,n+3,··· ,N}. 以下Alice 逐步定義對應(yīng)xi的有向圖, 記作G(i).

對于i ∈{1,2,··· ,n+1}, 每個G(i) 只有兩個頂點(diǎn), 分別稱為起點(diǎn)和終點(diǎn); 從起點(diǎn)到終點(diǎn)的有向邊賦值為xi.

對于i ∈{n+2,n+3,··· ,N}, 設(shè){G(1),G(2),··· ,G(i-1)}已經(jīng)定義完畢, 在以下兩種情形下分別定義G(i).

· 情形一: 如果Oi=+, 定義G(i) 為G(a(i)) 和G(b(i)) 的并聯(lián), 即G(a(i)) 與G(b(i)) 的起點(diǎn)合并為G(i) 的起點(diǎn),G(a(i)) 與G(b(i)) 的終點(diǎn)合并為G(i) 的終點(diǎn). 這里需要做一個合并操作, 如果某個頂點(diǎn)到另一個頂點(diǎn)的有向邊有多個, 則合并為一個有向邊, 其賦值為原來多個有向邊的賦值之和, 即賦值之異或.

· 情形二: 如果Oi=×, 定義G(i) 為G(a(i)) 和G(b(i)) 的串聯(lián), 即G(a(i)) 的起點(diǎn)就是G(i) 的起點(diǎn),G(a(i)) 的終點(diǎn)與G(b(i)) 的起點(diǎn)合并為一個頂點(diǎn),G(b(i)) 的終點(diǎn)就是G(i) 的終點(diǎn).

容易看出每個G(i) 都是單起點(diǎn)、單終點(diǎn)的有向無環(huán)圖, 任意兩個頂點(diǎn)之間至多有一個有向邊, 任意一個有向邊的賦值都是自變量x的一次函數(shù). 設(shè)|G(i)| 代表有向圖G(i) 的規(guī)模, 即頂點(diǎn)個數(shù), 則有:

可見有向圖G(i) 的規(guī)模呈爆炸式增長. 特別地, 當(dāng)N是多項(xiàng)式大時,|G(N)| 未必仍然是多項(xiàng)式大.

2.4 IK00 garbling 方案[10] 的第二步: 隨機(jī)多項(xiàng)式組成的矩陣

設(shè)|G(N)|=T,T多項(xiàng)式大. Alice 順序做以下三步操作.

(1) 將G(N) 的T個頂點(diǎn)按照任何一種偏序排列, 取這樣的T×T矩陣M0, 其(i,i) 元素為常數(shù)1,而當(dāng)i/=j時, (i,j) 元素為有向圖G(N) 的(i,j) 邊賦值. 于是M0是一個主對角線為常數(shù)1 的上三角矩陣.

(2) 取矩陣M1為M0去掉第一列和最后一行的(T-1)×(T-1) 矩陣. 于是M1的行列式恰好等于C(x).

(3) 取矩陣L和R為兩個行列式均為1 的(T-1)×(T-1) 隨機(jī)矩陣, 記M=LM1R. 于是M的行列式恰好等于C(x). 我們稱M為C(x) 的garbled 電路.

對于一組輸入值x1,x2,··· ,xn, Alice 將對應(yīng)的M發(fā)送給Bob. Bob 即使不知道C(x) 的拓?fù)浣Y(jié)構(gòu),他仍然能夠計(jì)算M的行列式.

3 GKP+13 可復(fù)用garbling 方案[5]

本節(jié)回顧GKP+13 可復(fù)用garbling 方案, 我們將分為高層結(jié)構(gòu)、中層結(jié)構(gòu)、底層結(jié)構(gòu)來敘述該方案.不失一般性, 總設(shè)Alice 為混淆者, Bob 為計(jì)算者.

3.1 高層結(jié)構(gòu): 可復(fù)用的garbling= 函數(shù)加密+ 對稱加密

GKP+13 可復(fù)用garbling 方案的設(shè)計(jì)思路是, 如果對任一個多項(xiàng)式時間可計(jì)算的布爾函數(shù)都存在函數(shù)加密方案, 則對任一個多項(xiàng)式時間可計(jì)算的布爾電路都存在可復(fù)用的garbled 電路. 請注意這里并不需要某個函數(shù)類的函數(shù)加密方案, 只需要單個函數(shù)的函數(shù)加密方案(single key functional encryption).Alice 使用這個函數(shù)加密方案. Alice 還使用一個對稱加密算法E(·,·), 其中的兩個位置依次為明文位置和密鑰位置;E(·,·) 對應(yīng)的解密算法為D(·,·), 其中的兩個位置依次為密文位置和密鑰位置; 設(shè)解密密鑰與加密密鑰相同. 對于布爾電路C(x), Alice 順序做以下四步操作.

(1) 計(jì)算C*=E(C,k0), 即將電路C的所有信息表示成一個比特串, 用對稱密鑰k0對其加密.

(2) 取f(x,k) = (D(C*,k))(x), 即f(x,k) 為如下電路: 先計(jì)算D(C*,k) 的值, 再以此值作為電路作用于輸入值x, 得到電路輸出值. 容易看出, 當(dāng)k=k0時f(x,k0) =C(x); 當(dāng)k為其他值時f(x,k) 與C(x) 相互獨(dú)立. 設(shè)x為n維布爾向量,k為l維布爾向量, 于是(x,k) 為n+l維布爾向量.

(3) 生成一個函數(shù)加密方案, 以及方案關(guān)于此f的對應(yīng)解密密鑰K0. 即, 將密文用K0解密, 則得到

f(明文).

(4) 記C=(C*,K0), 將此C作為原電路C的可復(fù)用garbled 電路, 發(fā)送給Bob.

對于一個輸入值x, Alice 調(diào)用函數(shù)加密方案的加密算法, 對(x,k0) 加密, 然后把密文發(fā)送給Bob.Bob 用f的對應(yīng)解密密鑰K0, 將密文解密為f(x,k0)=C(x).

3.2 中層結(jié)構(gòu): 函數(shù)加密= 屬性加密+ 全同態(tài)加密+ 不可復(fù)用的garbling

多項(xiàng)式時間可計(jì)算函數(shù)的函數(shù)加密方案是否存在? 這個問題一直都是挑戰(zhàn). 慶幸的是, 多項(xiàng)式時間可計(jì)算函數(shù)的屬性加密方案是現(xiàn)成的. 于是GKP+13 方案的設(shè)計(jì)者們自行設(shè)計(jì)了一個函數(shù)加密方案, 其結(jié)構(gòu)是屬性加密+ 全同態(tài)加密+ 不可復(fù)用的garbling. 需要說明的是, 此處使用的屬性加密方案并非原始的屬性加密, 而是屬性加密2. 具體來說, 屬性加密2 的解密者并不是只有當(dāng)手中的函數(shù)值為1 時才能正確解密, 而是: 當(dāng)手中的函數(shù)值為1 時能解密一半明文; 當(dāng)手中的函數(shù)值為0 時能解密另一半明文. 不難想象, 將原始的屬性加密擴(kuò)展為 屬性加密2 是容易的.

在函數(shù)加密的密鑰生成階段, Alice 順序做以下六步操作.

(1) 構(gòu)造一個可以加密單比特明文的全同態(tài)加密方案. 其中的(全同態(tài)加密密鑰, 對應(yīng)的解密密鑰) 作為可變參數(shù).

(2) 取f為3.1 節(jié)中的n+l維布爾函數(shù). 對于n+l個單比特明文, 構(gòu)造它們的f函數(shù)關(guān)于n+l個全同態(tài)密文的對應(yīng)同態(tài)函數(shù)f*. 請注意f*是n+l個全同態(tài)密文和全同態(tài)加密密鑰的函數(shù), 因此當(dāng)(全同態(tài)加密密鑰, 對應(yīng)的解密密鑰) 還沒確定時,f*的形式已經(jīng)確定了.

(3) 將f*表示為分量布爾函數(shù)的形式:f*= (f*1,f*2,··· ,f*λ), 其中每個f*i都是全同態(tài)密文和全同態(tài)加密密鑰的布爾函數(shù),λ為分量布爾函數(shù)的個數(shù).

(4) 構(gòu)造λ個 屬性加密2 方案, 分別記為ABE2,1, ABE2,2,···, ABE2,λ. 其中每個方案的(屬性加密密鑰, 對應(yīng)的解密密鑰) 作為固定參數(shù).

(5) 對于每個ABE2,i,i=1,2,··· ,λ, 生成布爾函數(shù)f*i對應(yīng)的解密密鑰ki. 具體地說,ki的作用如下. 設(shè)一個ABE2,i的密文是明文(p0,p1) 的對應(yīng)密文, 密文后邊還附有一個公開的標(biāo)簽label.則當(dāng)f*i(label)=1 時,ki只能解密得到p1; 當(dāng)f*i(label)=0 時,ki只能解密得到p0.

(6) 將{(f*i,ki),i= 1,2,··· ,λ}發(fā)送給Bob. 換句話說,{(f*i,ki),i= 1,2,··· ,λ}就是3.1 節(jié)中的函數(shù)加密密鑰K0.

在函數(shù)加密的加密階段, Alice 順序做以下六步操作.

(1) 對于函數(shù)加密的明文x= (x1,x2,··· ,xn), 調(diào)用3.1 節(jié)中的對稱加密密鑰k0= (k0,1,k0,2,···,k0,l), 得到全同態(tài)加密的n+l個單比特明文.

(2) 臨時選取全同態(tài)加密方案的(全同態(tài)加密密鑰, 對應(yīng)的解密密鑰), 對上述n+l個單比特明文分別進(jìn)行全同態(tài)加密, 得到n+l個全同態(tài)密文ψ1,ψ2,··· ,ψn+l. 記ψ=(ψ1,ψ2,··· ,ψn+l), 作為所有屬性加密密文后附的標(biāo)簽.

(3) 計(jì)算f*(ψ,全同態(tài)加密密鑰)=(f*1(ψ,全同態(tài)加密密鑰),f*2(ψ,全同態(tài)加密密鑰),··· ,f*λ(ψ,全同態(tài)加密密鑰)), 并將其記為ψ*= (ψ*1,ψ*2,··· ,ψ*λ). 值得注意的是, 用全同態(tài)的解密密鑰和解密電路就可以把ψ*解密為f(x,k0)=C(x). 但是, 全同態(tài)的解密密鑰和解密電路是需要隱藏的.

我們對以上的函數(shù)加密方案做如下注解: 該方案也可以單獨(dú)提煉出來, 作為獨(dú)立的函數(shù)加密方案使用.此時, 密鑰生成可以交給系統(tǒng)來做, 加密者Alice 可以不知道解密者Bob 的解密密鑰K0, 但必須知道并私藏對稱密鑰k0和全同態(tài)解密密鑰.

3.3 底層結(jié)構(gòu): 不可復(fù)用的garbling=BHR12 garbling 方案

顯然, 3.2 節(jié)中所用的不可復(fù)用garbling 方案是BHR12 garbling 方案而非IK00 garbling 方案. 因此我們必須給出以下四個注解.

4 方案分析和簡化方案

4.1 GKP+13 方案的效率

我們對GKP+13 可復(fù)用garbling 方案的評價是: 龐大的尺寸、一般的功能、概念上的可復(fù)用garbling、實(shí)際結(jié)構(gòu)中的不可復(fù)用garbling, 原因如下.

經(jīng)過我們的分析, GKP+13 可復(fù)用garbling 方案的構(gòu)造過程如下. 首先, 由隨機(jī)編碼和對稱加密算法構(gòu)造出不可復(fù)用的garbling; 其次, 由一般屬性加密構(gòu)造 屬性加密2; 再次, 由 屬性加密2 和全同態(tài)加密以及不可復(fù)用的garbling 構(gòu)造單函數(shù)的函數(shù)加密; 最后, 由單函數(shù)的函數(shù)加密和對稱加密算法構(gòu)造出可復(fù)用的garbling.

如此龐大的尺寸, 僅僅實(shí)現(xiàn)了可復(fù)用的garbling. 我們知道可復(fù)用的garbling 并不是密碼高級功能,因?yàn)樗冀K需要Alice 向Bob 隱藏一部分, 泄露另一部分, 而不是Bob 自主操作, 因而其功能級別遠(yuǎn)低于多線性映射和obfuscation.

不僅如此, 每次調(diào)用GKP+13 可復(fù)用garbling 方案, 都需要調(diào)用另一個新鮮電路的不可復(fù)用garbling. 因此, GKP+13 garbling 方案是概念上的可復(fù)用garbling, 實(shí)際結(jié)構(gòu)中的不可復(fù)用garbling.

4.2 GKP+13 方案的安全性漏洞和安全性冗余

4.3 GKP+13 方案的簡化方案

根據(jù)4.2 節(jié)的分析, 我們的簡化方案是把全同態(tài)密鑰的生成從函數(shù)加密的加密階段提前到函數(shù)加密的密鑰生成階段. 于是在函數(shù)加密的加密階段, 無需臨時生成全同態(tài)密鑰, 而全同態(tài)解密密鑰的保密性由不可復(fù)用garbling 的隨機(jī)編碼來實(shí)現(xiàn), 容易看出安全性沒有任何損失. 具體方案如下.

在函數(shù)加密的密鑰生成階段, Alice 順序做以下六步操作.

(1) 構(gòu)造一個可以加密單比特明文的全同態(tài)加密方案, 并生成(全同態(tài)加密密鑰, 對應(yīng)的解密密鑰) 作為固定參數(shù).

5 結(jié)論

本文深入探索了GKP+13 可復(fù)用garbling 方案的構(gòu)造過程和安全性, 指出該方案本質(zhì)上是不可復(fù)用的, 并提出一種簡化方案以降低原方案的尺寸. 未來我們將研究其它garbling 方案的可復(fù)用性, 特別地,我們將證明IK00 garbling 方案也不可復(fù)用.