胡予濮，董思越，王保倉，劉 君

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

1 前言

Garbling 是一個(gè)有著多重應(yīng)用的密碼原語.Garbling 主要適用于權(quán)力受限的場(chǎng)景，其中最早的應(yīng)用是安全多方計(jì)算(MPC)[1，2].隨后出現(xiàn)的應(yīng)用有屬性加密(ABE)和函數(shù)加密(FE)，有意思的是garbling和FE 常?；榈讓咏Y(jié)構(gòu)[3，4].Garbling 還被應(yīng)用于不可區(qū)分混淆(indistinguishability obfuscation，IO)[5-7].注意到garbling 和obfuscation 的中文翻譯同為“混淆”，說明garbling 和IO 有相似的功能，但后者的定義更強(qiáng)大.

1.1 Garbling 的兩個(gè)基本場(chǎng)景

Garbling 的所有應(yīng)用都源于以下兩個(gè)基本場(chǎng)景，是這兩個(gè)基本場(chǎng)景的組合或變形.

關(guān)于上述兩個(gè)基本場(chǎng)景，我們有以下三個(gè)注解.

注解1 基本場(chǎng)景一中的“定向選擇不經(jīng)意傳輸” 是容易實(shí)現(xiàn)的.

注解2 基本場(chǎng)景一就是多方安全計(jì)算的底層結(jié)構(gòu).以用戶U1和用戶U2的兩方安全計(jì)算為例，設(shè)用戶U1知道x1，用戶U2知道x2，雙方都知道電路C(·，·).雙方希望共同計(jì)算C(x1，x2) 的值，但U1需要隱藏x1，U2需要隱藏x2.于是，首先取f(·)C(x1，·)，U1和U2在基本場(chǎng)景一中分別扮演Alice 和Bob，使U2獲得f(x2)C(x1，x2).其次取f(·)C(·，x2)，U1和U2位置互換，在基本場(chǎng)景一中分別扮演Bob 和Alice，使U1獲得f(x1)C(x1，x2).兩次使用基本場(chǎng)景一，就使用戶U1和用戶U2都得到C(x1，x2)(正確性);但U1不知道x2，U2不知道x1(隱私性).

注解3 基本場(chǎng)景二不能成為多方安全計(jì)算的底層結(jié)構(gòu).這是因?yàn)樵诨緢?chǎng)景二中，一方擁有的知識(shí)包含了另一方擁有的知識(shí)，不符合多方安全計(jì)算的場(chǎng)景設(shè)置.

1.2 可復(fù)用garbling 及我們以往的工作

2013 年以前的garbling 方案[1，2，8，9]都是一次性garbling.即一次編碼(基本場(chǎng)景一或基本場(chǎng)景二)只能計(jì)算一個(gè)f和一個(gè)x的組合值f(x)，否則將不能保證隱私性.Goldwasser 等人[3]和Agrawal[4]提出了可復(fù)用garbling 方案.從字面意思來理解，可復(fù)用garbling 似乎滿足以下標(biāo)準(zhǔn): 一次編碼能計(jì)算一個(gè)f和任意多個(gè)x的組合值f(x)，同時(shí)保證隱私性(如果是這樣的話，可復(fù)用garbling 就是IO 了).然而我們[10]對(duì)可復(fù)用garbling 的有效性進(jìn)行了分析，指出它只達(dá)到了一個(gè)更弱的標(biāo)準(zhǔn): 對(duì)f的一次編碼確實(shí)可以用來計(jì)算多個(gè)x的組合值f(x)，但對(duì)變量(值或域) 的一次編碼只能計(jì)算一個(gè)x的組合值f(x).這就是說，可復(fù)用garbling 實(shí)際上仍然是一個(gè)一次性garbling.

1.3 本文的工作

本文繼續(xù)討論可復(fù)用garbling 的可用性和效率.本文指出以下兩點(diǎn): (1) 即使可復(fù)用garbling 被當(dāng)作一次性garbling 使用，也常常是不可用的，它只能用于兩個(gè)基本場(chǎng)景中的基本場(chǎng)景二，不能用于基本場(chǎng)景一.結(jié)合本文前述的注解3 可知，可復(fù)用garbling 至少不能用于安全多方計(jì)算(MPC).(2) 即使可復(fù)用garbling 被當(dāng)作一次性garbling 用于基本場(chǎng)景二，沒有證據(jù)表明它比原來的一次性garbling 效率更高.本文工作的細(xì)節(jié)如下.為了說明第(1) 點(diǎn)，本文首先指出對(duì)變量的編碼并不是與f相互獨(dú)立的，而是要用到f的信息.換句話說，對(duì)變量的編碼可以看作對(duì)f的編碼的另一部分.在此基礎(chǔ)上，本文說明在可復(fù)用garbling 方案中，要么Alice 的知識(shí)包含Bob 的知識(shí)，要么Bob 的知識(shí)包含Alice 的知識(shí)，因此不符合基本場(chǎng)景一的場(chǎng)景設(shè)置.為了說明第(2) 點(diǎn)，我們仔細(xì)討論可復(fù)用garbling 的中層結(jié)構(gòu)和底層結(jié)構(gòu)(由于我們[11]已經(jīng)指出Agrawal 的中層結(jié)構(gòu)/底層結(jié)構(gòu)[4]不可用，因此只能討論Goldwasser 等人的中層結(jié)構(gòu)/底層結(jié)構(gòu)[3]).在此基礎(chǔ)上，我們將可復(fù)用garbling 方案與一個(gè)以前的一次性garbling 方案[9]進(jìn)行比較.我們說明，當(dāng)前者不使用全同態(tài)加密技術(shù)中的自舉(Bootstrapping) 和降模(Modular switching) 運(yùn)算時(shí)，前者的計(jì)算復(fù)雜度遠(yuǎn)遠(yuǎn)高于后者的計(jì)算復(fù)雜度;當(dāng)前者使用自舉或降模運(yùn)算時(shí)，兩者的比較非常復(fù)雜，但沒有跡象顯示前者的計(jì)算復(fù)雜度更低.

2 BHR12: 主流的一次性garbling 方案

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

布爾函數(shù)的一般表達(dá)式是按照運(yùn)算順序來表示每一步的{兩個(gè)輸入比特，運(yùn)算符號(hào)，一個(gè)輸出比特}.設(shè)運(yùn)算符號(hào)集為{+，×}，其中‘‘+” 為比特異或，‘‘×” 為比特與，則n維布爾函數(shù)f(x) 的一般表達(dá)式如下.

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

· 對(duì)于in+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.其中xNf(x).

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

2.2 BHR12 garbling 方案的基本場(chǎng)景一[9]

取兩個(gè)公開的概率分布X0和X1，這兩個(gè)概率分布能夠完全區(qū)分.取一個(gè)公開的對(duì)稱加密算法E(·，·)，其中的兩個(gè)位置依次為明文位置和密鑰位置.

2.2.1 編碼(Alice)

第一步(隨機(jī)設(shè)定): 對(duì)于每個(gè)i1，2，···，N-1，隨機(jī)選取一個(gè)0，1}，然后定義Xi，0Xj，Xi，1X1-jmod 2.對(duì)于iN，定義Xi，0X0，Xi，1X1.

2.2.2 傳輸(Alice→Bob)

2.2.3 計(jì)算(Bob)

2.3 BHR12 garbling 方案的基本場(chǎng)景二[9]

基本場(chǎng)景二與基本場(chǎng)景一的唯一區(qū)別是，Alice 不是將變量域編碼用“定向選擇不經(jīng)意傳輸” 的方式發(fā)給Bob，而是直接根據(jù)x的值對(duì)進(jìn)行選擇，然后將選擇的結(jié)果發(fā)給Bob.這就是說，Alice 的知識(shí)是{x，f}，Bob 的知識(shí)僅僅是f(x).

3 可復(fù)用garbling 方案[3，4]

本節(jié)回顧可復(fù)用garbling 方案，我們將分為高層結(jié)構(gòu)、中層結(jié)構(gòu)、底層結(jié)構(gòu)來敘述該方案.

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

使用一個(gè)對(duì)稱加密算法E(·，·)，其中的兩個(gè)位置依次為明文位置和密鑰位置，對(duì)應(yīng)的解密算法為D(·，·).使用一個(gè)公鑰函數(shù)加密算法E′(·，·)，其中的兩個(gè)位置依次為明文位置和主公鑰位置;當(dāng)主私鑰為K、函數(shù)為g時(shí)，對(duì)應(yīng)的解密鑰記為S(K，g)，解密得到明文m的函數(shù)值g(m);對(duì)應(yīng)的解密算法為D′(·，·).高層結(jié)構(gòu)分為以下的編碼、傳輸、計(jì)算三部分.

3.1.1 編碼

(1) 對(duì)于函數(shù)f，取定對(duì)稱密鑰k0，計(jì)算f*E(f，k0).即將電路f表示成一個(gè)比特串，用對(duì)稱密鑰k0加密.

(2) 取f**(x，k)(D(f*，k))(x).即f**(x，k) 為如下電路: 先計(jì)算比特串FD(f*，k)，再將此比特串F作為電路作用于輸入值x，得到輸出值F(x).(容易看出，當(dāng)kk0時(shí)f**(x，k)f**(x，k0)f(x)，當(dāng)k為其他值時(shí)f**(x，k) 與f(x) 無關(guān))

(3) 生成公鑰函數(shù)加密的主公鑰和主私鑰{mpk，msk}，并計(jì)算對(duì)應(yīng)msk 和函數(shù)f**的解密鑰S(msk，f**).記SS(msk，f**).

(4) (電路f的編碼) 記(f*，S)，就是原電路f的編碼.這個(gè)可以在多個(gè)x計(jì)算f(x) 時(shí)重復(fù)使用，因此被稱為可復(fù)用garbling 的電路編碼.

(5) (變量域或變量值的編碼) 對(duì)任意x，計(jì)算E′((x，k0)，mpk)，就是變量值x的編碼.

3.1.2 傳輸

3.1.3 計(jì)算

3.2 中層結(jié)構(gòu): 函數(shù)加密=屬性加密+全同態(tài)加密+一次性garbling [3]

Goldwasser 等人[3]和Agrawal[4]各自為可復(fù)用garbling 的高層結(jié)構(gòu)設(shè)計(jì)了函數(shù)加密方案.由于我們[11]已經(jīng)指出，Agrawal 的函數(shù)加密方案[4]是無效的，因此只回顧Goldwasser 等人的函數(shù)加密方案[3].該方案的結(jié)構(gòu)是屬性加密+全同態(tài)加密+一次性garbling.其中的屬性加密方案不是原始的ABE，而是擴(kuò)展版的ABE2.具體來說，ABE2的解密者并不是只有當(dāng)手中的函數(shù)值為1 時(shí)才能正確解密，而是: 當(dāng)手中的函數(shù)值為1 時(shí)能解密一半;當(dāng)手中的函數(shù)值為0 時(shí)能解密另一半.將原始的ABE 擴(kuò)展為ABE2是容易的.

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

(1) 構(gòu)造一個(gè)全同態(tài)加密方案.其中的{全同態(tài)加密密鑰，對(duì)應(yīng)的解密密鑰} 作為每次加密時(shí)的可變參數(shù).

(2) 取3.1.1 小節(jié)中的布爾函數(shù)f**，構(gòu)造f**關(guān)于全同態(tài)密文的同態(tài)函數(shù)f***.請(qǐng)注意f***是全同態(tài)密文的函數(shù).

(3) 將f***表示為分量布爾函數(shù)的形式:f***其中每個(gè)都是全同態(tài)密文的布爾函數(shù)，λ為分量布爾函數(shù)的個(gè)數(shù)(我們知道λ「log2，其中q是全同態(tài)加密方案中所使用的模).

(4) 構(gòu)造λ個(gè)ABE2方案，分別記為ABE2，1，ABE2，2，···，ABE2，λ.這些方案的屬性加密密鑰作為固定參數(shù)，共同成為3.1.1 小節(jié)中的K0.

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

(6){(，ki)，i1，2，···，λ}作為固定參數(shù)，成為3.1.1 小節(jié)中的S(msk，f**).在函數(shù)加密的加密階段，順序做以下六步操作:

(1) 取3.1.1 小節(jié)中的(x，k0) 為明文.

(2) 臨時(shí)選取全同態(tài)加密方案的{全同態(tài)加密密鑰，對(duì)應(yīng)的解密密鑰}，對(duì)(x，k0) 做全同態(tài)加密，得到全同態(tài)密文ψ.ψ將作為所有屬性加密密文后附的標(biāo)簽.

3.3 底層結(jié)構(gòu): 一次性garbling=BHR12 garbling 方案[9]

BHR12 garbling 方案完全適合用于中層結(jié)構(gòu)里的一次性garbling，因?yàn)锽HR12 方案對(duì)電路類型基本上沒有限制，只要多項(xiàng)式時(shí)間可計(jì)算.而其他一些一次性garbling 方案(如文獻(xiàn)[8]) 限制電路為常數(shù)深度.BHR12 方案的另一個(gè)優(yōu)勢(shì)是不需特殊的密碼工具，只需要對(duì)稱加密算法.而其他一些一次性garbling方案則使用分支程序或隨機(jī)化矩陣等特殊工具.

3.4 我們對(duì)可復(fù)用garbling 的已有分析結(jié)果[10]

我們?cè)赋?，可?fù)用garbling 沒有達(dá)到“一次編碼多次計(jì)算”，只能達(dá)到“對(duì)電路的一次編碼可以用于多次計(jì)算”，而對(duì)變量域或變量值的一次編碼只能用于一次計(jì)算.這就是說，可復(fù)用garbling 實(shí)際上仍然是一個(gè)一次性garbling.

4 可復(fù)用garbling 的可用性分析

本文繼續(xù)討論可復(fù)用garbling 的可用性和效率，只不過將其當(dāng)作一次性garbling 來使用.本節(jié)討論的問題是: 它能否用于第1 節(jié)中描述的基本場(chǎng)景一.

4.1 在基本場(chǎng)景一中的可用性

首先，對(duì)變量值x的編碼不僅要知道x，還要知道k0，而k0是f的信息的一部分:E(f，k0)f*，fD(f*，k0).換句話說，對(duì)x的編碼可以看作是對(duì)f的編碼的另一部分，即對(duì)f的完整編碼不是而是

其次，我們關(guān)注高層結(jié)構(gòu).總設(shè)Alice 做電路f的編碼，于是Alice 知道電路f.

如果Alice 做變量域或變量值的編碼，則她必須知道變量值x.于是Alice 的知識(shí)是{x，f}，Bob 的知識(shí)僅僅是f(x).

如果Bob 做變量域或變量值的編碼，則他不但要知道x，也要知道k0.另外，Bob 肯定知道f*(因?yàn)閒*是的一部分)，而且由{f*，k0}立刻得到f:fD(f*，k0).于是Alice 的知識(shí)為f，Bob 的知識(shí)為{x，f}.

綜上所述，無論是Alice 還是Bob 做變量編碼，一方的知識(shí)總是包含另一方的知識(shí)，不符合基本場(chǎng)景一的知識(shí)分布.因此，即使可復(fù)用garbling 被當(dāng)作一次性garbling 使用，它至少不能用于安全多方計(jì)算.

4.2 關(guān)于一種補(bǔ)救方法的說明

Goldwasser 等人[12]提出了“多輸入函數(shù)加密” 方案.如果用這個(gè)方案替代高層結(jié)構(gòu)中的函數(shù)加密方案，則不但能使可復(fù)用 garbling 用于基本場(chǎng)景一，而且能獲得更強(qiáng)的可復(fù)用性，即 IO.具體地說，利用多輸出函數(shù)加密方案的 “分散加密集中解密” 特點(diǎn)，在函數(shù)加密的加密階段 (3.1.1 小節(jié)第 (5) 步)，{E′(x，mpk)，E′(k0，mpk)}，而不是xE′((x，k0)，mpk);在函數(shù)加密的解密階段(3.1.3 小節(jié))，將E′(x，mpk) 和E′(k0，mpk) 兩個(gè)密文集中在一起進(jìn)行解密，得D′(，S)D′((E′(x，mpk)，E′(k0，mpk))，S)f(x).做了這樣的改變之后，把E′(x，mpk) 的計(jì)算交給Bob，把E′(k0，mpk) 的計(jì)算交給Alice.于是Alice 提交的所有內(nèi)容都是可復(fù)用的，Bob 可以任意多次計(jì)算而不必每次都與Alice 交互.

然而，這個(gè)“多輸入函數(shù)加密” 方案的底層結(jié)構(gòu)都是IO.我們知道，IO 如果存在，其本身就是強(qiáng)大的可復(fù)用garbling，根本不用再構(gòu)造成另一個(gè)體制.可復(fù)用garbling 的構(gòu)造避免使用IO，就是為了避免巨大的尺寸和難以清晰的安全性.

5 可復(fù)用garbling 的效率分析

本節(jié)將可復(fù)用garbling 當(dāng)作一次性garbling，用于基本場(chǎng)景二(見第1 節(jié))，將其與BHR12 方案[9]進(jìn)行比較.設(shè)變量x的長度為n，f作為比特串的長度為n′，f作為布爾函數(shù)的尺寸為N.設(shè)可復(fù)用garbling 方案和BHR12 方案使用的對(duì)稱加密方案相同，都是E(·，·) 和D(·，·).設(shè)E(·，·) 的電路尺寸為N′(注意到E(·，·) 是多輸出布爾電路，從單輸出布爾電路的尺寸推廣到多輸出布爾電路的尺寸是容易的).根據(jù)對(duì)稱加密體制的現(xiàn)狀，D(·，·) 的電路尺寸應(yīng)該稍大于N′.設(shè)可復(fù)用garbling 方案中使用的屬性加密體制的個(gè)數(shù)為λ，我們知道λ「log2，q為全同態(tài)加密方案的模.

5.1 BHR12 garbling 方案的計(jì)算復(fù)雜度

BHR12 方案在編碼階段的主要計(jì)算是4(N-n-1) 個(gè)對(duì)稱加密.在編碼階段的其他計(jì)算為2N-1次抽樣和(N-n-1) 次隨機(jī)排序，其中每次隨機(jī)排序是對(duì)四個(gè)數(shù)字的排序.

BHR12 方案在計(jì)算階段的計(jì)算是4(N-n-1) 個(gè)對(duì)稱解密，其中的N-n-1 個(gè)對(duì)稱解密為解密成功，另外3(N-n-1) 個(gè)解密為解密失敗.

5.2 我們的兩個(gè)觀察

第一個(gè)觀察: 當(dāng)可復(fù)用garbling 方案不使用全同態(tài)加密技術(shù)中的自舉(bootstrapping)和降模(modular switching) 運(yùn)算時(shí)，一般有λ ＞4N.理由如下.

由于f作為布爾函數(shù)的電路尺寸為N，且D(·，·) 的電路尺寸稍大于N′，因此f**作為布爾函數(shù)的電路尺寸稍大于N+N′.這就是說，f**是順序做大約N+N′個(gè)布爾運(yùn)算.作為f**的密文同態(tài)函數(shù)，f***應(yīng)該是順序做大約N+N′個(gè)模q運(yùn)算，而且f**和f***的依次運(yùn)算類型相互對(duì)應(yīng): 一個(gè)比特異或?qū)?yīng)一個(gè)模q加法運(yùn)算，一個(gè)比特與運(yùn)算對(duì)應(yīng)一個(gè)模q乘法運(yùn)算.現(xiàn)在我們考慮這些模q運(yùn)算所造成的全同態(tài)密文噪聲尺寸的累積.設(shè)原始噪聲的平均尺寸為e，考慮到全同態(tài)加密方案的安全性，一般取e為多項(xiàng)式大，因此設(shè)log2e ≥8 是合理的.然后設(shè)N+N′個(gè)模q運(yùn)算中有大約一半是模q加法運(yùn)算，另一半是模q乘法運(yùn)算.模q加法會(huì)使噪聲尺寸增加，但影響不大，此處忽略.模q乘積的噪聲尺寸是原來噪聲尺寸的乘積，因此個(gè)模q乘法得到的噪聲尺寸平均大約是.而在全同態(tài)加密方案中，防止解密出錯(cuò)的一個(gè)前提是q ＞2·.最后我們得到

第二個(gè)觀察: 當(dāng)可復(fù)用garbling 方案不使用全同態(tài)加密技術(shù)中的自舉和降模運(yùn)算時(shí)，可復(fù)用garbling方案中的一個(gè)(屬性加密，屬性解密) 的計(jì)算復(fù)雜度高于一個(gè)(E(·，·)，D(·，·)) 的計(jì)算復(fù)雜度.理由如下.

注意到f***.f**中的一個(gè)布爾運(yùn)算對(duì)應(yīng)f***中的一個(gè)模q運(yùn)算;而對(duì)于每個(gè)i1，2，···，λ，f***中的一個(gè)模q運(yùn)算對(duì)應(yīng)的遠(yuǎn)遠(yuǎn)不止一個(gè)布爾運(yùn)算.換句話說，每個(gè)的電路尺寸都遠(yuǎn)遠(yuǎn)大于f**的電路尺寸，也就遠(yuǎn)遠(yuǎn)大于N+N′.另一方面，根據(jù)主流KP-ABE 方案的結(jié)構(gòu)[13，14]，對(duì)于布爾函數(shù)中的每個(gè)布爾運(yùn)算O，ABE2，i的解密算法中總有一組對(duì)應(yīng)操作O′，其中O′的計(jì)算復(fù)雜度遠(yuǎn)遠(yuǎn)超過兩個(gè)布爾運(yùn)算的計(jì)算復(fù)雜度.我們稱O′為O的擬同態(tài)運(yùn)算.綜上所述，一個(gè)(屬性加密，屬性解密) 的計(jì)算復(fù)雜度遠(yuǎn)遠(yuǎn)高于2(N+N′) 個(gè)布爾運(yùn)算，而一個(gè)(E(·，·)，D(·，·)) 的計(jì)算復(fù)雜度稍高于2N′個(gè)布爾運(yùn)算.

5.3 計(jì)算復(fù)雜度的比較: 不使用自舉和降模運(yùn)算

BHR12 方案的主要計(jì)算是大約4N個(gè)(E(·，·)，D(·，·)).可復(fù)用garbling 的主要計(jì)算是λ個(gè)(屬性加密，屬性解密)，全同態(tài)加密方案的(密鑰生成，同態(tài)運(yùn)算)，以及一個(gè)一次性garbling (仍然是一個(gè)BHR12方案).根據(jù)我們的兩個(gè)觀察(見5.2 小節(jié))，可復(fù)用garbling 的計(jì)算復(fù)雜度遠(yuǎn)遠(yuǎn)高于BHR12 方案.

5.4 計(jì)算復(fù)雜度的比較: 使用自舉或降模運(yùn)算

綜上所述，此時(shí)計(jì)算復(fù)雜度的比較非常復(fù)雜，但沒有跡象顯示BHR12 方案比使用自舉或降模運(yùn)算的可復(fù)用garbling 方案有更高的計(jì)算復(fù)雜度.