韓 帥，劉勝利，3，谷大武

1.上海交通大學(xué) 電子信息與電氣工程學(xué)院，上海200240

2.密碼科學(xué)技術(shù)全國(guó)重點(diǎn)實(shí)驗(yàn)室，北京100878

3.成都衛(wèi)士通信息產(chǎn)業(yè)股份有限公司 摩石實(shí)驗(yàn)室，北京100070

1 引言

功能加密(functional encryption，F(xiàn)E)[1-3]是一種靈活的加密模式，由Boneh 等人于2011 年[1]首次提出并給出正式定義.通過對(duì)傳統(tǒng)加密的推廣和擴(kuò)展，功能加密支持密文上的精細(xì)化訪問控制.傳統(tǒng)的加密方案如公鑰加密方案(public-key encryption，PKE) 提供了“全有或全無(wú)” 的訪問控制，僅私鑰sk 的持有者能夠從密文中解密恢復(fù)出明文消息，而其他任何人都不能從密文中獲得關(guān)于明文的任何信息.而功能加密提供了更為精細(xì)的訪問控制.具體而言，功能加密的訪問控制能力由一個(gè)函數(shù)族F所刻畫.私鑰sk 的持有者可以為函數(shù)族F中的任一函數(shù)生成一個(gè)功能密鑰skf.持有功能密鑰skf者對(duì)一個(gè)加密消息x的密文ct 進(jìn)行解密，僅能獲得函數(shù)值f(x)，而對(duì)x的其它信息一無(wú)所知.

一般而言，根據(jù)支持的函數(shù)族F，功能加密可以分為兩類.第一類功能加密可以支持所有多項(xiàng)式時(shí)間可計(jì)算的函數(shù)[4-7].雖然這類功能加密支持的函數(shù)族非常大，但是其構(gòu)造往往非常復(fù)雜，需要使用不可區(qū)分混淆[6]、多線性映射[8]等很強(qiáng)的密碼工具.因此，這類功能加密難以實(shí)際應(yīng)用在現(xiàn)實(shí)場(chǎng)景中.第二類功能加密僅支持一些特殊的函數(shù)族，如內(nèi)積函數(shù)族[9-14]、二次函數(shù)族[15-19]等.這類功能加密往往構(gòu)造較為高效，無(wú)需使用不可區(qū)分混淆、多線性映射等復(fù)雜密碼工具，更適合應(yīng)用于現(xiàn)實(shí)場(chǎng)景中.雖然這類功能加密支持的函數(shù)族比較有限，但是在很多實(shí)際場(chǎng)景中都能夠滿足應(yīng)用需求.

本文將主要研究支持內(nèi)積函數(shù)族的功能加密，簡(jiǎn)記為內(nèi)積功能加密(inner-product FE，IPFE).具體而言，內(nèi)積功能加密所加密的消息為一個(gè)向量Zm，所生成的功能密鑰也與一個(gè)向量Zm相關(guān).使用向量y對(duì)應(yīng)的功能密鑰sky來(lái)對(duì)向量x的密文ct 進(jìn)行解密可以得到內(nèi)積值〈x，y〉Z.實(shí)際上，內(nèi)積功能加密可以滿足許多實(shí)際場(chǎng)景的應(yīng)用需求，例如用來(lái)計(jì)算明文數(shù)據(jù)的析取、合取、加權(quán)平均值等多種統(tǒng)計(jì)信息，適用于生物特征認(rèn)證、近鄰搜索和統(tǒng)計(jì)分析等多種應(yīng)用場(chǎng)景[9，20，21].

內(nèi)積功能加密的安全性.內(nèi)積功能加密的常規(guī)安全性要求為選擇明文/密文攻擊下的不可區(qū)分性(indistinguishability under chosen-plaintext/ciphertext attacks，IND-CPA/CCA).IND-CPA 安全性要求概率多項(xiàng)式時(shí)間的敵手A無(wú)法區(qū)分向量x0的密文和向量x1的密文，即使A可以通過功能密鑰查詢獲得許多功能密鑰: 每一次查詢時(shí)，A提交一個(gè)向量y，并獲得對(duì)應(yīng)的功能密鑰sky.為了防止平凡攻擊，我們要求A僅能獲得滿足〈x0，y〉〈x1，y〉 的向量y所對(duì)應(yīng)的功能密鑰.這里的向量x0、x1以及A進(jìn)行功能密鑰查詢的向量y都可以由敵手A適應(yīng)性地選擇.IND-CCA 安全性比IND-CPA 更強(qiáng)，還允許敵手A進(jìn)行解密查詢: 每一次查詢時(shí)，A提交一個(gè)向量y和一個(gè)密文ct，并獲得使用功能密鑰sky對(duì)ct進(jìn)行解密的結(jié)果.

2016 年，Agrawal 等人[10]分別基于標(biāo)準(zhǔn)的DDH(decisional Diffie-Hellman)、LWE(learning-witherrors) 和DCR (decisional composite residuosity) 假設(shè)，給出了多個(gè)滿足IND-CPA 安全性的內(nèi)積功能加密方案.同年，Zhang 等人[22]基于DDH 假設(shè)構(gòu)造了首個(gè)IND-CCA 安全的內(nèi)積功能加密方案.隨后，Benhamouda 等人[11]基于DCR 假設(shè)也得到了IND-CCA 安全的內(nèi)積功能加密方案.此外，Tomida[12]和Liu 等人[13，14]還分別給出了具有緊致安全規(guī)約的IND-CPA 和IND-CCA 安全性的內(nèi)積功能加密方案.

抗泄漏安全性.IND-CPA 和IND-CCA 安全性中實(shí)際上隱含一個(gè)非常理想的假設(shè)，即假設(shè)密鑰sk對(duì)于敵手A而言是完全保密的.而在實(shí)際的密碼學(xué)應(yīng)用中，密碼方案還面臨著密鑰泄漏等安全威脅.通過使用側(cè)信道攻擊技術(shù)[23-25]，敵手可以對(duì)密碼設(shè)備運(yùn)行時(shí)的功耗、時(shí)間、電磁輻射、微波等信息進(jìn)行分析，進(jìn)而獲得密鑰sk 的部分信息.在安全模型中，通常用密鑰泄漏查詢來(lái)刻畫這一攻擊能力: 每一次查詢時(shí)，A可以提交一個(gè)函數(shù)L，并獲得由函數(shù)L指定的密鑰信息L(sk).抗泄漏(leakage-resilient，LR) 安全性要求對(duì)于能夠進(jìn)行密鑰泄漏查詢的敵手A，密碼方案仍然是安全的.具體而言，抗泄漏CPA/CCA 安全性要求IND-CPA/CCA 安全性在敵手A能夠進(jìn)行密鑰泄漏查詢時(shí)仍然成立.本文，我們將主要考慮有界泄漏模型[26，27]，即要求敵手通過泄漏查詢獲得的密鑰總泄漏比特?cái)?shù)|L(sk)| 小于密鑰的總比特?cái)?shù)|sk|.特別地，抗泄漏安全性所容許的最大泄漏比特?cái)?shù)|L(sk)| 與密鑰比特?cái)?shù)|sk| 之間的比值|L(sk)|/|sk| 稱為泄漏率(leakage rate).

目前，抗泄漏安全性的研究主要集中在傳統(tǒng)的公鑰加密方案[26-29]、基于身份加密方案[30-37]、基于屬性加密方案[31，37-39]等，而關(guān)于功能加密的研究工作相對(duì)較少[40-45].下面對(duì)已有的抗泄漏安全功能加密的相關(guān)工作進(jìn)行介紹.1在功能加密的抗泄漏安全性相關(guān)工作中，部分工作[40–42] 所研究的功能加密與Boneh 等人于2011 年[1] 提出的功能加密(也即本文所考慮的功能加密) 不同，它們所考慮的功能加密仍然是一種“全有或全無(wú)” 的密文訪問控制: 在加密時(shí)除了輸入明文消息x 還會(huì)輸入一個(gè)元素a;而使用功能密鑰skf 解密時(shí)，要么在f(a)=1 時(shí)恢復(fù)出整個(gè)明文x，要么在f(a)=0 時(shí)無(wú)法獲得明文的任何信息.因此，這里未對(duì)這些工作進(jìn)行詳細(xì)介紹.

— 2018 年，Wang 等人[43]正式為功能加密定義了抗泄漏安全性，并基于混淆電路技術(shù)構(gòu)造了抗泄漏CCA 安全的功能加密方案.該方案的抗泄漏CCA 安全性可以基于DDH 假設(shè)或者DCR 假設(shè)，且支持的泄漏率達(dá)到了-o(1).但是該工作中考慮的抗泄漏CCA 安全性較弱: 其允許敵手獲得私鑰sk 的泄漏信息，但僅允許敵手A進(jìn)行1 次功能密鑰查詢(即僅能獲得1 個(gè)功能密鑰skf)，且敵手A需要在游戲一開始就提交消息x0，x1以及要進(jìn)行功能密鑰查詢的函數(shù)f(因此不是適應(yīng)性的).此外，雖然該功能加密方案可以支持所有多項(xiàng)式時(shí)間可計(jì)算的函數(shù)，但是由于使用了混淆電路的技術(shù)，構(gòu)造較為復(fù)雜.

— 2020 年，Zhang 等人[44，45]研究了內(nèi)積功能加密的抗泄漏安全性，并基于抗泄漏的內(nèi)積哈希證明系統(tǒng)技術(shù)構(gòu)造了抗泄漏CPA 安全的內(nèi)積功能加密方案.該方案基于DDH 假設(shè)，且在內(nèi)積函數(shù)的向量維數(shù)為m時(shí)，支持的泄漏率為-o(1).該工作中考慮的抗泄漏CPA 安全性也相對(duì)較弱:

其不允許敵手A獲得(主) 私鑰sk 的泄漏信息，僅允許敵手獲得功能密鑰sky的泄漏信息.目前已有的功能加密方案達(dá)到的抗泄漏安全性較弱，如何構(gòu)造具有較強(qiáng)抗泄漏安全性的功能加密方案仍然是一個(gè)尚未解決的問題.

本文貢獻(xiàn).在本文中，我們?cè)O(shè)計(jì)了第一個(gè)達(dá)到適應(yīng)性抗泄漏CCA 安全性的內(nèi)積功能加密方案.

· 首先，給出了本文所考慮的抗泄漏CCA 安全性的正式定義.我們考慮的抗泄漏CCA 安全性是適應(yīng)性的，允許敵手A適應(yīng)性地進(jìn)行下面四種查詢: 進(jìn)行(主) 私鑰sk 的泄漏查詢、功能密鑰sky的泄漏查詢、功能密鑰sky的查詢以及解密查詢.2為了防止平凡攻擊，要求A 僅能對(duì)滿足〈x0，y〉= 〈x1，y〉 條件的向量y 進(jìn)行功能密鑰查詢.但我們對(duì)功能密鑰sky 泄漏查詢的向量y 沒有這一要求.因此敵手A 可以對(duì)滿足上述條件的y 進(jìn)行功能密鑰查詢，而對(duì)不滿足上述條件的y 仍然可以進(jìn)行功能密鑰的泄漏查詢.這是為什么本文的安全模型同時(shí)允許敵手進(jìn)行功能密鑰泄漏查詢和功能密鑰查詢的原因.關(guān)于本文安全模型的更多解釋和說(shuō)明請(qǐng)參見第3 節(jié)中的注1.其正式定義請(qǐng)參見第3 節(jié).因此，我們考慮的抗泄漏CCA 安全性比已有工作中考慮的功能加密抗泄漏安全性[43-45]都要強(qiáng).

· 然后，基于非對(duì)稱配對(duì)群構(gòu)造了一個(gè)內(nèi)積功能加密方案，并在標(biāo)準(zhǔn)模型以及標(biāo)準(zhǔn)的MDDH (matrix decisional Diffie-Hellman) 假設(shè)[46]下證明了本文方案滿足上述較強(qiáng)的抗泄漏CCA 安全性.MDDH 假設(shè)包含了標(biāo)準(zhǔn)的DDH 假設(shè)和k-Linear(k-LIN) 假設(shè)[46]，因此通過我們的構(gòu)造實(shí)際上可以分別得到基于DDH 假設(shè)和k-LIN 假設(shè)的抗泄漏CCA 安全內(nèi)積功能加密方案.本文方案是第一個(gè)達(dá)到適應(yīng)性抗泄漏CCA 安全的內(nèi)積功能加密方案.方案的具體構(gòu)造及其抗泄漏CCA 安全性證明請(qǐng)參見第4 節(jié).

表1 中將本文構(gòu)造的內(nèi)積功能加密方案所達(dá)到的抗泄漏CCA 安全性與已有工作[43-45]進(jìn)行了對(duì)比，其中“?” 表示具有該性質(zhì)，“×” 表示不具有該性質(zhì)，“—” 表示未考慮該性質(zhì)，“(···)” 中標(biāo)明了方案所支持的泄漏率，“m” 為內(nèi)積函數(shù)的向量維數(shù).

表1 抗泄漏安全功能加密方案的抗泄漏安全性比較Table 1 Leakage-resilient security comparison of leakage-resilient secure FE schemes

2 預(yù)備知識(shí)

本節(jié)將介紹文中使用的符號(hào)和基本工具，然后給出內(nèi)積功能加密及MDDH 假設(shè)的定義.

2.1 符號(hào)說(shuō)明和基本工具

首先對(duì)所使用的符號(hào)進(jìn)行說(shuō)明.N 表示自然數(shù)集合，Z 表示整數(shù)集合.本文統(tǒng)一用N 表示安全參數(shù)，并且默認(rèn)所有的算法、概率分布、函數(shù)以及敵手都會(huì)將1λ作為一個(gè)隱含的輸入.本文中的所有算法如無(wú)特殊說(shuō)明都是概率算法.對(duì)于集合X，x ←$X表示從集合X中均勻選取元素x.對(duì)于概率分布D，x ←$D表示按照概率分布D選取元素x.對(duì)于算法A，y ←$A(x) 表示算法A以x作為輸入時(shí)的運(yùn)行結(jié)果為y.如果A是確定性算法，將其記作y ←A(x).“PPT” 為概率多項(xiàng)式時(shí)間(probabilistic polynomial-time) 的簡(jiǎn)記.poly 表示多項(xiàng)式函數(shù)，negl 表示可忽略函數(shù).

本文中的所有向量如無(wú)特殊說(shuō)明都是列向量.對(duì)于向量x，x?表示它的轉(zhuǎn)置，‖x‖∞表示它的無(wú)窮范數(shù)，即x的所有分量中絕對(duì)值的最大值.

對(duì)于兩個(gè)向量x，Zm，〈x，y〉 表示它們的內(nèi)積x?yZ.

對(duì)于隨機(jī)變量X和Y，X的最小熵定義為H∞(X) :-log(maxxPr[Xx])，X和Y的統(tǒng)計(jì)距離定義為Δ(X，Y):

定義 1(抗碰撞哈希函數(shù)) 一個(gè)哈希函數(shù)族H是抗碰撞的，如果對(duì)于任意PPT 敵手A，滿足:Pr[H ←$H，(x1，x2)←$A(H):x1/x2∧H(x1)H(x2)]≤negl(λ).

2.2 內(nèi)積功能加密

下面給出內(nèi)積功能加密的語(yǔ)義以及正確性要求.與文獻(xiàn)[10，12] 等工作一樣，我們考慮的內(nèi)積函數(shù)〈x，y〉 為多項(xiàng)式有界的，即要求‖x‖∞≤X，‖y‖∞≤Y，其中上界X和Y為關(guān)于安全參數(shù)λ的多項(xiàng)式.

定義2(內(nèi)積功能加密) 令Xpoly(λ) 和Ypoly(λ) 為內(nèi)積函數(shù)的多項(xiàng)式上界.一個(gè)內(nèi)積功能加密方案IPFE(Par，Setup，KGen，Enc，Dec) 由如下五個(gè)PPT 算法組成:

· pp←$Par: 參數(shù)生成算法Par 生成一個(gè)公開系統(tǒng)參數(shù)pp.為了方便起見，pp 會(huì)默認(rèn)作為所有其他算法的一個(gè)輸入.

· (mpk，msk)←$Setup(1m): 設(shè)置算法Setup 輸入內(nèi)積函數(shù)的向量維數(shù)N，生成一對(duì)主公鑰/主私鑰(mpk，msk).為了方便起見，mpk 會(huì)默認(rèn)作為KGen 和Dec 算法的一個(gè)輸入.

· sky ←$KGen(msk，y): 密鑰生成算法KGen 輸入主私鑰msk 和一個(gè)向量Zm，生成一個(gè)功能密鑰sky.

· ct←$Enc(mpk，x): 加密算法Enc 輸入主公鑰mpk 和一個(gè)向量Zm，生成一個(gè)密文ct.

·d/⊥←Dec(sky，ct): 解密算法Dec 輸入一個(gè)功能密鑰sky和一個(gè)密文ct，輸出一個(gè)解密結(jié)果Z 或者一個(gè)代表解密失敗的特殊符號(hào)⊥.

正確性要求: 對(duì)所有的N，x，Zm，‖x‖∞≤X，‖y‖∞≤Y，pp←$Par，(mpk，msk)←$Setup(1m)，sky ←$KGen(msk，y) 和ct←$Enc(mpk，x)，都一定有Dec(sky，ct)〈x，y〉 成立.

接下來(lái)給出內(nèi)積功能加密的選擇明文/密文攻擊下的不可區(qū)分性(indistinguishability under chosenplaintext/ciphertext attacks，IND-CPA/CCA) 定義.

如果不允許敵手A在圖1 中描述的實(shí)驗(yàn)進(jìn)行ODEC查詢，則稱IPFE 是IND-CPA 安全的.

圖1 內(nèi)積功能加密IPFE 的IND-CCA 安全實(shí)驗(yàn)Figure 1 IND-CCA security experiment for IPFE

2.3 MDDH 假設(shè)

令l，N 且滿足l ＞k.我們稱一個(gè)概率分布Dl，k為矩陣分布，如果它的輸出都是上的滿秩矩陣.不失一般性，假設(shè)A ←$Dl，k的前k行線性無(wú)關(guān).一個(gè)特殊的矩陣分布為均勻矩陣分布Ul，k，其輸出為上的均勻矩陣.如果lk+1，則記Dk:Dk+1，k，Uk:Uk+1，k.

下面回顧MDDH (matrix decisional Diffie-Hellman) 假設(shè).

MDDH 假設(shè)包括了許多標(biāo)準(zhǔn)假設(shè).例如通過將矩陣分布Dl，k實(shí)例化為如下的LIN1 和LIN k:

得到的LIN1-MDDH 假設(shè)和LIN k-MDDH 假設(shè)實(shí)際上分別就是標(biāo)準(zhǔn)的DDH 假設(shè)和k-Linear(k-LIN)假設(shè)[46].MDDH 假設(shè)還包括了標(biāo)準(zhǔn)的SXDH (symmetric external DH) 假設(shè)，即要求DDH 假設(shè)同時(shí)在群G1和群G2上成立.

Dl，k-MDDH 假設(shè)與均勻矩陣分布的Ul，k-MDDH 假設(shè)之間有密切的關(guān)系，下面回顧文獻(xiàn)[46，49] 中建立的結(jié)論.

KerMDH(Kernel Matrix DH) 假設(shè)[50]是MDDH 假設(shè)的一個(gè)計(jì)算版本，下面回顧其定義.

下面的引理表明Dl，k-MDDH 假設(shè)比Dl，k-KerMDH 假設(shè)更強(qiáng)，因?yàn)槲覀兛梢院苋菀子脻M足x?A0的非零向量[x]3-s來(lái)高效地判斷一個(gè)向量[u]s是否在span([A]s) 中.

3 內(nèi)積功能加密的抗泄漏安全性

本節(jié)給出內(nèi)積功能加密的抗泄漏安全性定義，包括抗泄漏CPA 和抗泄漏CCA (leakage-resilience under chosen plaintext/ciphertext attacks，LR-CPA/CCA) 兩種安全性定義.

定義6(抗泄漏CPA/CCA 安全性) 令N 表示容許的泄漏比特?cái)?shù).一個(gè)內(nèi)積功能加密方案IPFE(Par，Setup，KGen，Enc，Dec) 是κ-LR-CCA 安全的，如果對(duì)于任意PPT 敵手A，滿足

顯然，當(dāng)κ0 時(shí)，κ-LR-CPA/CCA 安全性就退化為定義3 中的IND-CPA/CCA 安全性.下面對(duì)抗泄漏CPA/CCA 安全性的形式化進(jìn)行說(shuō)明.

注1(關(guān)于抗泄漏CPA/CCA 安全性的形式化) 在圖2 描述的實(shí)驗(yàn)中，敵手A可以適應(yīng)性地進(jìn)行四種查詢:

圖2 內(nèi)積功能加密IPFE 的LR-CCA 安全實(shí)驗(yàn)，其中|·| 代表比特長(zhǎng)度Figure 2 LR-CCA security experiment for IPFE，where |·| denotes bit-length

— 通過功能密鑰查詢OKGEN(y)，A可以獲得功能密鑰sky;

— 通過解密查詢ODEC(y，ct)，A可以獲得ct 在功能密鑰sky下的解密結(jié)果;

— 通過功能密鑰泄漏查詢OLEAK(y，L)，A可以獲得關(guān)于功能密鑰sky的部分泄漏信息L(sky);

— 通過主私鑰泄漏查詢OMLEAK(L)，A可以獲得關(guān)于主私鑰msk 的部分泄漏信息L(msk).特別地，最后兩種查詢OLEAK和OMLEAK是與圖1 中描述的IND-CCA 安全實(shí)驗(yàn)相比新增的地方，刻畫了A的泄漏攻擊能力.由于本文考慮有界泄漏模型[26，27]，因此我們要求A通過OLEAK和OMLEAK獲得的密鑰總泄漏量不超過κ比特，這由圖2 中的變量?及相關(guān)判斷條件所刻畫.此外，A可以在整個(gè)實(shí)驗(yàn)過程中適應(yīng)性地提交一對(duì)挑戰(zhàn)向量(x0，x1)，并獲得xβ的加密結(jié)果ct*作為挑戰(zhàn)密文，其中β為A需要猜測(cè)的挑戰(zhàn)比特.因此，我們定義的抗泄漏CPA/CCA 安全性是完全適應(yīng)性的.

為了防止平凡攻擊，我們對(duì)敵手A的查詢有如下限制:

·A進(jìn)行的所有OKGEN(y) 查詢必須滿足〈x0，y〉〈x1，y〉;否則A可以使用sky對(duì)挑戰(zhàn)密文ct*進(jìn)行解密，計(jì)算出〈xβ，y〉，進(jìn)而成功恢復(fù)出β.

·A不能對(duì)挑戰(zhàn)密文ct*進(jìn)行ODEC查詢;否則A很容易通過解密結(jié)果知道β的值.上面兩個(gè)限制條件與圖1 中描述的IND-CCA 安全實(shí)驗(yàn)中一樣.此外，對(duì)于敵手A的OLEAK和OMLEAK查詢，我們有如下限制:

·A不能在收到挑戰(zhàn)密文ct*之后繼續(xù)進(jìn)行OLEAK和OMLEAK查詢;否則A很容易通過OLEAK或OMLEAK查詢獲得β的值.具體而言，A在收到挑戰(zhàn)密文ct*后，可以選擇一個(gè)滿足〈x0，y〉/〈x1，y〉 的向量y，定義一個(gè)以功能密鑰sky為輸入、輸出僅為1 比特的特殊函數(shù)L:

然后進(jìn)行一次OLEAK查詢(y，L)，就可以通過1 比特泄漏信息L(sky) 知道β的值.類似地，A也可以定義一個(gè)以主私鑰msk 為輸入、輸出僅為1 比特的特殊函數(shù)L:

然后進(jìn)行一次OMLEAK查詢(L)，就可以通過1 比特泄漏信息L(msk) 知道β的值.

該限制條件與已有的公鑰加密方案的抗泄漏安全性定義[26，27]以及內(nèi)積功能加密方案的抗泄漏安全性定義[44，45]類似，均不允許敵手在獲得挑戰(zhàn)密文之后繼續(xù)獲得關(guān)于密鑰的泄漏信息.

4 抗泄漏CCA 安全的內(nèi)積功能加密方案與安全性證明

本節(jié)將基于非對(duì)稱配對(duì)群構(gòu)造一個(gè)抗泄漏CCA 安全的內(nèi)積功能加密方案，并在標(biāo)準(zhǔn)模型和標(biāo)準(zhǔn)的MDDH 假設(shè)下證明其抗泄漏CCA 安全性.本文方案是第一個(gè)達(dá)到適應(yīng)性抗泄漏CCA 安全性的內(nèi)積功能加密方案.

具體而言，4.1 節(jié)將給出內(nèi)積功能加密方案的具體構(gòu)造，4.2 節(jié)給出其基于MDDH 假設(shè)的抗泄漏CCA安全性證明.

4.1 內(nèi)積功能加密方案構(gòu)造

令PGGen 為非對(duì)稱配對(duì)群的生成算法.令Dk和U(m+k+2)，k為兩個(gè)矩陣分布，其中N 為MDDH 假設(shè)的參數(shù)，N 為內(nèi)積函數(shù)的向量維數(shù).令H是一族從{0，1}*到Zp的抗碰撞哈希函數(shù).令Xpoly(λ) 和Ypoly(λ) 為內(nèi)積函數(shù)的多項(xiàng)式上界.圖3 中給出內(nèi)積功能加密方案IPFE(Par，Setup，KGen，Enc，Dec) 的具體構(gòu)造.

圖3 基于MDDH 假設(shè)構(gòu)造的內(nèi)積功能加密方案IPFE=(Par，Setup，KGen，Enc，Dec)Figure 3 Construction of scheme IPFE=(Par，Setup，KGen，Enc，Dec) based on MDDH

首先說(shuō)明構(gòu)造的內(nèi)積功能加密方案IPFE 滿足正確性要求.對(duì)于任意向量Zm的密文ct([c]1，[d]1，[e]1)，我們有[c]1:[A]1s，[d]1:[W A]1s+[x]1以及[e]1:[(K0+τK1)A]1s，因此可以得到

故能夠通過解密算法Dec 的驗(yàn)證.進(jìn)一步，對(duì)于任意向量Zm，使用其功能密鑰sky(-y?W，y) 對(duì)ct 進(jìn)行解密，可以得到

因此對(duì)于多項(xiàng)式有界的‖x‖∞≤X和‖y‖∞≤Y，解密算法Dec 可以在[-mXY，mXY] 范圍內(nèi)求解出離散對(duì)數(shù)dy?x，進(jìn)而成功計(jì)算出內(nèi)積值y?x〈x，y〉.

從技術(shù)層面來(lái)說(shuō)，本文的內(nèi)積功能加密方案IPFE 可以看成是有機(jī)結(jié)合和改造了Agrawal 等人提出的IND-CPA 安全的內(nèi)積功能加密方案[10](這對(duì)應(yīng)于我們密文ct 中的[c]1和[d]1) 以及Kiltz 和Wee提出的具有一次模擬健壯性(one-time simulation-soundness) 的非交互零知識(shí)證明系統(tǒng)[51](這對(duì)應(yīng)于我們密文ct 中的[e]1，其本質(zhì)上是在證明[c]1屬于線性空間span([A]1)).但是我們強(qiáng)調(diào)，Agrawal 等人的方案以及Kiltz 和Wee 提出的系統(tǒng)均未考慮密鑰泄漏.為了實(shí)現(xiàn)適應(yīng)性的抗泄漏CCA 安全性，我們將他們的技術(shù)在密鑰泄漏場(chǎng)景下進(jìn)行了改造.此外，我們密文ct 中的[c]1和[d]1部分與文獻(xiàn)[10] 中的方案僅僅是結(jié)構(gòu)類似，而維數(shù)卻非常不同.為了能夠證明適應(yīng)性的抗泄漏安全性，我們將文獻(xiàn)[10] 中IND-CPA安全內(nèi)積功能加密方案的密文中2 維的[c]1擴(kuò)展到了m+k+2 維的[c]1，這使得我們可以借助統(tǒng)計(jì)性的復(fù)雜性杠桿(complexity leveraging) 技術(shù)[52]來(lái)證明適應(yīng)性安全性(即允許敵手A在整個(gè)實(shí)驗(yàn)過程中的任意時(shí)刻提交挑戰(zhàn)向量(x0，x1)).相應(yīng)地，我們將文獻(xiàn)[51] 的非交互零知識(shí)證明系統(tǒng)進(jìn)行了調(diào)整，使其能夠證明更高維數(shù)的[c]1.一方面，密文ct 中的[e]1部分可以幫助我們?cè)诮饷軙r(shí)拒絕一些由敵手“非法” 生成的密文，從而實(shí)現(xiàn)CCA 安全性.另一方面，由于[e]1的生成過程[e]1[(K0+τK1)A]1s以及[e]1的驗(yàn)證過程e([c?]1，[(+)B]2)e([e?]1，[B]2) 都是可以公開計(jì)算的，即僅需要使用公開的pp 和mpk，因此[e]1的生成和驗(yàn)證不會(huì)在主私鑰msk 和功能密鑰sky中引入更多元素，這幫助我們最終能夠在保持抗泄漏安全性的同時(shí)實(shí)現(xiàn)CCA 安全性.

4.2 節(jié)將基于Dk-MDDH 假設(shè)證明本文的內(nèi)積功能加密方案IPFE 是κ-LR-CCA 安全的，其中容許的泄漏比特?cái)?shù)κ ≤logp-2λ.這里，我們對(duì)IPFE 方案的效率和泄漏率進(jìn)行分析.令x·G 表示群G中的x個(gè)元素.當(dāng)MDDH 參數(shù)為k、內(nèi)積函數(shù)的向量維數(shù)為m時(shí)，IPFE 方案的公開系統(tǒng)參數(shù)pp 包含(k2+k)·G2，主公鑰mpk 包含(2mk+3k2+4k)·G1+(2mk+2k2+4k)·G2，主私鑰msk 包含(m2+mk+2m)·Zp，功能密鑰sky包含(m+k+2)·Zp，3IPFE 方案的功能密鑰為sky :=(-y?W，y)，其中y 是公開的、無(wú)需秘密保存，因此這里未將它計(jì)入sky 的大小中.密文ct 包含(2m+2k+3)·G1，解密Dec計(jì)算mk+2k2+3k個(gè)配對(duì)運(yùn)算.

4.2 內(nèi)積功能加密方案的抗泄漏CCA 安全性證明

下面給出所設(shè)計(jì)內(nèi)積功能加密方案IPFE 的抗泄漏CCA 安全性定理以及安全性證明.

定理1(IPFE 的抗泄漏CCA 安全性) 令容許的泄漏比特?cái)?shù)κ ≤logp-2λ且內(nèi)積函數(shù)的多項(xiàng)式上界X ＜.4“X ＜/4” 這一要求實(shí)際上自然是成立的，因?yàn)閜 為配對(duì)群的階數(shù)， p 至少為2λ 比特的，故/4 為安全參數(shù)λ 的指數(shù)大小，顯然遠(yuǎn)大于多項(xiàng)式大小的X=poly(λ).如果Dk-MDDH 假設(shè)在群G1和群G2上均成立，同時(shí)H是抗碰撞哈希函數(shù)，則圖3 中構(gòu)造的內(nèi)積功能加密方案IPFE 是κ-LR-CCA 安全的.

具體而言，對(duì)于任意PPT 敵手A，其攻擊IPFE 的κ-LR-CCA 安全性且進(jìn)行最多Q次ODEC查詢，存在PPT 敵手B1，B2，B3，使得

證明:我們將通過定義一系列不可區(qū)分的游戲 G0—G5來(lái)進(jìn)行證明，其中游戲 G0為原始的安全實(shí)驗(yàn)，而在游戲G5中敵手A攻破安全性的優(yōu)勢(shì)幾乎為0.為了方便起見，表2 中給出了這些游戲的簡(jiǎn)要描述，并用灰色標(biāo)記出相鄰兩個(gè)游戲間的差別.我們用Pri[·]表示某個(gè)事件在游戲Gi中發(fā)生的概率.

表2 內(nèi)積功能加密方案IPFE 的抗泄漏CCA 安全性證明中游戲G0—G5 的簡(jiǎn)要描述Table 2 Brief description of games G0–G5 for LR-CCA security proof of IPFE

游戲G0: 該游戲?yàn)镮PFE 的實(shí)驗(yàn)(參見圖2).令事件Win 表示β′β.根據(jù)定義可知

— 通過OKGEN(y)查詢，A可以獲得功能密鑰sky(-y?W，y);通過OLEAK(y，L)查詢，A可以獲得泄漏信息L(sky)L(-y?W，y);通過OMLEAK(L) 查詢，A可以獲得泄漏信息L(msk)L(W).A通過OLEAK和OMLEAK獲得的密鑰總泄漏量不超過κ比特.

— 在收到A的ODEC(y，ct([c]1，[d]1，[e]1)) 查詢時(shí)，挑戰(zhàn)者如下進(jìn)行回復(fù).挑戰(zhàn)者首先判斷是否有ct/ct*∧e([c?]1，[(+)B]2)e([e?]1，[B]2) 成立，其中τ:H([c]1，[d]1).如果不成立，則挑戰(zhàn)者直接輸出⊥給A.如果成立，則挑戰(zhàn)者計(jì)算[d]1:-y?W[c]1+y?[d]1，并在[-mXY，mXY] 范圍內(nèi)求解離散對(duì)數(shù)d.如果能夠求解得到d，挑戰(zhàn)者將解密結(jié)果d輸出給A;否則，挑戰(zhàn)者輸出⊥給A.

— 在收到挑戰(zhàn)向量(x0，x1) 時(shí)，挑戰(zhàn)者如下生成挑戰(zhàn)密文ct*:([c*]1，[d*]1，[e*]1): 挑戰(zhàn)者均勻選取s*←$計(jì)算[c*]1:[A]1s*，[d*]1:[W A]1s*+[xβ]1，τ*:H([c*]1，[d*]1)Zp和[e*]1:[(K0+τ*K1)A]1s*.

為了防止平凡攻擊，敵手A進(jìn)行的所有OKGEN(y) 查詢必須滿足〈x0，y〉〈x1，y〉，且A不能在獲得挑戰(zhàn)密文ct*之后繼續(xù)進(jìn)行OLEAK和OMLEAK查詢.

游戲G1: 該游戲與上一游戲G0幾乎一樣，差別僅在于挑戰(zhàn)密文ct*的生成.在該游戲中，挑戰(zhàn)者在計(jì)算挑戰(zhàn)密文ct*([c*]1，[d*]1，[e*]1) 中的[d*]1和[e*]1時(shí)，按如下方式進(jìn)行計(jì)算: [d*]1:W[c*]1+[xβ]1，[e*]1:(K0+τ*K1)[c*]1，即不再使用[c*]1[A]1s*中的向量s*.

由于[c*]1[A]1s*，因此這些變化只是形式上的，G1和G0本質(zhì)是相同的，故

游戲G2: 該游戲與上一游戲G1幾乎一樣，差別僅在于對(duì)解密查詢ODEC的回復(fù).在該游戲中，對(duì)于A的ODEC(y，ct([c]1，[d]1，[e]1)) 查詢，挑戰(zhàn)者的判斷條件改為:

如果上述條件不成立，則挑戰(zhàn)者直接輸出⊥給A.

為了分析Pr2[DecBad]，注意到事件DecBad 發(fā)生意味著

即[e?]1-[c?(+)]1為[B]2內(nèi)核(kernel) 里的一個(gè)非零向量.

根據(jù)引理3，Dk-MDDH 假設(shè)比Dk-KerMDH 假設(shè)更強(qiáng)，因此可知在計(jì)算意義上是很難找到[B]2內(nèi)核里的非零向量的.故在群G2上的Dk-MDDH 假設(shè)下，事件DecBad 幾乎不會(huì)發(fā)生，有Pr2[DecBad]≤(λ)+1/(p-1) 成立，從而命題1 得證.

游戲G3: 該游戲與上一游戲G2幾乎一樣，差別僅在于對(duì)解密查詢ODEC的回復(fù).在該游戲中，對(duì)于A的ODEC(y，ct([c]1，[d]1，[e]1)) 查詢，挑戰(zhàn)者的判斷條件進(jìn)一步改為:

其中τ:H([c]1，[d]1) 和τ*:H([c*]1，[d*]1) 分別為本次ODEC查詢中計(jì)算的標(biāo)簽以及挑戰(zhàn)密文ct*的生成過程中計(jì)算的標(biāo)簽.如果上述條件不成立，則挑戰(zhàn)者直接輸出⊥給A.

命題2基于H的抗碰撞性，有

證明:令事件TagColl 表示A進(jìn)行過某次ODEC查詢(y，ct([c]1，[d]1，[e]1))，使得有ct/ct*，[e]1[(K0+τK1)c]1，但ττ*成立.顯然G2和G3在事件TagColl 不發(fā)生的情況下是完全相同的，因此有

為了分析Pr3[TagColl]，我們將事件TagColl 分為以下兩種情況，并逐一進(jìn)行分析:

根據(jù)引理2，群G1上的Dk-MDDH 假設(shè)成立能推出Uk-MDDH 假設(shè)和U(m+k+2)，k-MDDH 假設(shè)均成立.而根據(jù)群G1上的U(m+k+2)，k-MDDH 假設(shè)，在計(jì)算意義上難以判斷[c*]1到底是從中均勻選取的還是從span([A]1){[A]1s*|s*}中選取的.因此，G3和G4是計(jì)算不可區(qū)分的，我們有

游戲G5: 該游戲與上一游戲G4幾乎一樣，差別僅在于對(duì)解密查詢ODEC的回復(fù).在該游戲中，對(duì)于A的ODEC(y，ct([c]1，[d]1，[e]1)) 查詢，挑戰(zhàn)者的判斷條件進(jìn)一步改為:

如果上述條件不成立，則挑戰(zhàn)者直接輸出⊥給A.

命題3

證明:令事件CBad 表示A進(jìn)行過某次ODEC查詢(y，ct([c]1，[d]1，[e]1))，使得有ct/ct*，[e]1[(K0+τK1)c]1，τ/τ*，但[c]1/span([A]1) 成立.顯然G4和G5在事件CBad 不發(fā)生的情況下是完全相同的，因此有

事件CBad 發(fā)生意味著A的某次ODEC查詢(y，ct([c]1，[d]1，[e]1)) 滿足ct/ct*，τ/τ*，[c]1/span([A]1)，以及

下面說(shuō)明A難以計(jì)算出滿足上述條件的[e]1.首先由于τ/τ*，因此上式中的(μ0+τμ1) 與A所獲得的信息(μ0+τ*μ1) 兩兩獨(dú)立，故對(duì)于A而言，(μ0+τμ1) 在Zp上均勻分布.此外，由于[c]1/span([A]1)，前面選擇的向量a⊥滿足(a⊥)?c/0.因此，對(duì)于A而言，上式中的(μ0+τμ1)b⊥(a⊥)?c這一項(xiàng)在span(b⊥){γb⊥|Zp}上均勻分布，從而A能計(jì)算出滿足上述條件的[e]1的概率不超過1/p.

根據(jù)上述分析，在A的一次ODEC查詢中，事件CBad 發(fā)生的概率不超過1/p.因此，在A的Q次ODEC查詢中，事件CBad 發(fā)生的概率不超過Q/p，即Pr5[CBad]≤Q/p，從而命題3 得證.

最后給出對(duì)Pr5[Win] 的分析.

命題4

證明:對(duì)于A提交的挑戰(zhàn)向量(x0，x1)，令Δx1-x0為其差值.由于我們考慮的是多項(xiàng)式有界內(nèi)積函數(shù)，因此‖x0‖∞≤X，‖x1‖∞≤X，即x0，x1[-X，X]m，故有Δx1-x0[-2X，2X]m.

綜上分析，除了ct*之外，A能獲得的關(guān)于u的信息最多只有κ比特.因此對(duì)于A而言，中至少還有(m+2)logp-κ比特的最小熵.

接下來(lái)分析G5中Win 發(fā)生的概率，即A能夠猜對(duì)β的概率.在挑戰(zhàn)密文ct*([c*]1，[d*]1，[e*]1)中，注意到僅[d*]1的計(jì)算涉及β:

綜上所有分析，結(jié)合式(2)—(4)以及命題1—4，可以得到式(1)成立.

因此圖3 中構(gòu)造的內(nèi)積功能加密方案IPFE 是κ—LR-CCA 安全的，定理1 得到證明.

4.3 抗泄漏安全功能加密方案的效率分析及比較

本小節(jié)對(duì)本文方案與已有的抗泄漏安全功能加密方案的效率進(jìn)行分析和比較.

第1 節(jié)中已介紹，目前抗泄漏安全功能加密的相關(guān)工作較少，僅有的方案包括Wang 等人[43]構(gòu)造的抗泄漏CCA 安全的功能加密方案以及Zhang 等人[44，45]構(gòu)造的抗泄漏CPA 安全的內(nèi)積功能加密方案.表1 中對(duì)這些方案的抗泄漏安全性進(jìn)行了比較.下面將對(duì)這些方案的效率進(jìn)行分析和比較，包括各項(xiàng)參數(shù)大小及算法運(yùn)行時(shí)間.

表3 中分析和對(duì)比這些方案的各項(xiàng)參數(shù)大小，包括主公鑰mpk、主私鑰msk、功能密鑰sky以及密文ct 的大小，其中表中的數(shù)字表示包含的群元素個(gè)數(shù)(如“m2+m” 表示包含m2+m個(gè)群元素)，“m” 為內(nèi)積函數(shù)的向量維數(shù)，“l(fā)ogp” 為群階p的比特長(zhǎng)度(在128 比特安全強(qiáng)度下，一般有l(wèi)ogp256).由表3 數(shù)據(jù)可知，本文方案的主公鑰mpk 大小比文獻(xiàn)[43] 方案要小(大約小m/4 倍)、比文獻(xiàn)[44，45] 方案稍大(大約大4 倍)，主私鑰msk 大小比文獻(xiàn)[43—45] 方案均要大(大約大m/2 倍)，功能私鑰sky大小比文獻(xiàn)[43—45] 方案均要小(大約小3 倍)，而密文ct 大小比文獻(xiàn)[43] 方案稍大(大約大2 倍)、比文獻(xiàn)[44，45]方案要小(至少小128·m+512 倍).總的來(lái)說(shuō)，本文方案的各項(xiàng)參數(shù)大小與已有方案[43-45]各有優(yōu)劣，而在最影響通信復(fù)雜度的密文ct 大小方面，本文方案比文獻(xiàn)[43] 方案稍大，但遠(yuǎn)小于文獻(xiàn)[44，45] 方案.

表3 抗泄漏安全功能加密方案的各項(xiàng)參數(shù)大小比較Table 3 Comparison of leakage-resilient secure FE schemes: Parameter sizes

圖4 中分析和對(duì)比了這些方案的算法運(yùn)行時(shí)間，包括設(shè)置算法Setup、密鑰生成算法KGen、加密算法Enc 以及解密算法Dec 在不同向量維數(shù)m下的運(yùn)行時(shí)間.運(yùn)行時(shí)間分析采用了libgnark 庫(kù)[53]中的BN254 曲線.由于文獻(xiàn)[43] 方案的KGen 和Dec 算法中分別涉及混淆電路的混淆算法和求值算法，其計(jì)算復(fù)雜度與混淆電路的層數(shù)、門數(shù)等參數(shù)息息相關(guān)，難以分析出實(shí)際的運(yùn)行時(shí)間，因此在圖4 的KGen 和Dec 算法的運(yùn)行時(shí)間中，我們僅分析和對(duì)比了文獻(xiàn)[44，45] 方案和本文方案.由圖4 數(shù)據(jù)可知，本文方案的設(shè)置算法Setup 比文獻(xiàn)[43] 方案快大約1—3 個(gè)數(shù)量級(jí)、比文獻(xiàn)[44，45] 方案稍慢(不超過1 個(gè)數(shù)量級(jí))，密鑰生成算法KGen 比文獻(xiàn)[44，45] 方案稍快(不超過1 個(gè)數(shù)量級(jí))，加密算法Enc 比文獻(xiàn)[43] 方案快大約2—7 個(gè)數(shù)量級(jí)、比文獻(xiàn)[44，45] 方案快大約1—3 個(gè)數(shù)量級(jí)，解密算法Dec 比文獻(xiàn)[44，45] 方案快大約2個(gè)數(shù)量級(jí).總的來(lái)說(shuō)，本文方案的算法運(yùn)行時(shí)間比已有方案[43-45]有較大優(yōu)勢(shì)，特別是在操作最為頻繁的加密算法Enc 和解密算法Dec 方面，本文方案比已有方案快1—7 個(gè)數(shù)量級(jí).

圖4 抗泄漏安全功能加密方案的算法運(yùn)行時(shí)間比較Figure 4 Comparison of leakage-resilient secure FE schemes: Running time of algorithms

5 總結(jié)

本文提出了第一個(gè)達(dá)到適應(yīng)性抗泄漏CCA 安全性的內(nèi)積功能加密方案.本文方案所達(dá)到的抗泄漏 CCA 安全性是完全適應(yīng)性的，允許敵手以任意的適應(yīng)性的方式進(jìn)行四種查詢，包括主私鑰泄漏查詢、功能密鑰泄漏查詢、功能密鑰查詢以及解密查詢，比已有工作中考慮的功能加密抗泄漏安全性[43-45]都要強(qiáng).所提方案為非對(duì)稱配對(duì)群上的直接構(gòu)造，不使用復(fù)雜的密碼原語(yǔ)，相較已有工作而言構(gòu)造更為簡(jiǎn)單.我們基于標(biāo)準(zhǔn)的MDDH 假設(shè)證明了方案的抗泄漏CCA 安全性，且方案支持的泄漏率優(yōu)于Zhang 等人[44，45]構(gòu)造的抗泄漏CPA 安全內(nèi)積功能加密方案.在本文工作的基礎(chǔ)上，如何進(jìn)一步提高抗泄漏CCA 安全內(nèi)積功能加密方案的效率以及支持的泄漏率可作為后續(xù)的研究方向.