基于單密鑰函數(shù)加密的具體高效可否認(rèn)加密方案*

楊 糠, 張 江

密碼科學(xué)技術(shù)國家重點實驗室, 北京 100878

1 引言

Canetti 等人[1]引入了可否認(rèn)加密(deniable encryption, DE) 的概念, 使得即使發(fā)送者/接收者在加密通信之后, 仍然能產(chǎn)生“否認(rèn)” 的(但與真實值不可區(qū)分的) 隨機數(shù)/私鑰, 打開密文為另一個不同的明文. 可否認(rèn)加密方案可從非交互的概念自然推廣到交互的概念(在交互的情況, 可否認(rèn)加密也稱為可否認(rèn)交互通信). 可否認(rèn)加密加強了傳統(tǒng)的安全通信, 使得即使發(fā)送者/接收者在之后被強迫泄露明文、隨機數(shù)或私鑰, 仍然能夠保證通信消息的機密性. 可否認(rèn)加密的一個直接應(yīng)用是抑制投票賄選, 其可否認(rèn)性保證: 即使惡意實體賄賂了投票人, 也無法確認(rèn)投票是否滿足指定要求. 可否認(rèn)加密滿足非承諾性(non-committing)[2], 從而可應(yīng)用到自適應(yīng)的安全多方計算(secure multi-party computation, MPC) 協(xié)議中[3]. 此外, 可否認(rèn)加密保證了在選擇打開攻擊(seletive opening attacks) 下的安全性[4,5], 也蘊含了不可強制安全多方計算(incoercible MPC) 的存在性[6,7].

Canetti 等人[1]提出了兩類可否認(rèn)性. 第一種是完全可否認(rèn)性, 即發(fā)送者和接收者運行一套預(yù)先指定的密鑰生成和加解密算法, 過后可否認(rèn)密文為其他的明文. 第二種是雙方案可否認(rèn)性(也稱為多分布可否認(rèn)性), 允許有兩套密鑰生成和加解密算法, 其中一套為可否認(rèn)算法, 另一套為正常算法, 使得在可否認(rèn)算法下加密的一個明文能被否認(rèn)為在正常算法下加密的另一個明文. 容易看到完全可否認(rèn)性是比雙方案可否認(rèn)性更強的安全概念.

我們自然期望設(shè)計滿足完全可否認(rèn)性的DE 方案. 然而, 設(shè)計該類加密方案是一個長期的公開問題.直到2014 年, Sahai 和Waters[8]才解決該公開問題, 基于不可區(qū)分混淆(indistinguishability obfuscation, iO) 設(shè)計了發(fā)送者完全可否認(rèn)的公鑰可否認(rèn)加密方案. Bendlin 等人[9]在2011 年給出了關(guān)于接收者完全可否認(rèn)性的不可能結(jié)果: 不存在滿足該類可否認(rèn)性的可否認(rèn)公鑰加密方案, 即任何接收者完全可否認(rèn)的方案要求交互通信. 然而, 設(shè)計接收者完全可否認(rèn)的交互方案一直保持是公開問題, 直到2020 年. 具體地, Canetti 等人[10]給出了一個突破性的結(jié)果, 基于亞指數(shù)安全的iO 設(shè)計了雙方完全可否認(rèn)的可否認(rèn)交互加密方案, 不僅允許發(fā)送者和接收者可以否認(rèn)密文, 而且當(dāng)否認(rèn)的明文不同時保證無法區(qū)分誰在欺騙.盡管完全可否認(rèn)DE 方案的公開問題已得到初步解決, 然而已知的構(gòu)造都依賴于iO, 即僅從理論上給出了完全可否認(rèn)方案的解決方法, 完全沒有考慮其效率問題. 本文集中于設(shè)計具體高效的可否認(rèn)加密方案, 從而考慮更弱的可否認(rèn)性——雙方案可否認(rèn)性.

在1997 年, Canetti 等人[1]基于半透明集合(translucent sets) 設(shè)計了發(fā)送者可否認(rèn)的雙方案可否認(rèn)公鑰加密方案, 其中半透明集合能夠通過陷門置換和Hard-core 謂詞獲得. 如果用RSA 陷門置換實例化該可否認(rèn)加密方案, 那么對于128 比特安全等級, 該方案每加密1 個比特需要800 字節(jié)的通信和256次RSA 加密運算. 從而, 該可否認(rèn)加密方案的效率仍然偏低. 在2011 年, O’Neill 等人[11]一般化該設(shè)計思想, 從雙半透明集合(bitranslucent sets) 設(shè)計了雙方可否認(rèn)的雙方案可否認(rèn)公鑰加密方案, 而且基于LWE 困難假設(shè)[12]提出了雙半透明集合的實例. 他們的方案獲得了更強的可否認(rèn)性(即允許發(fā)送者和接收者都可以否認(rèn)密文), 但他們方案的效率比Canetti 等人給出的方案更低. 此外, 雙方案可否認(rèn)的屬性基加密方案[13]和函數(shù)加密方案[14]也被相繼提出. 然而, 這些方案僅僅擴展了可否認(rèn)加密方案的功能性,并沒有改進該類加密方案的效率.

與發(fā)送者可否認(rèn)的DE 方案比較, 接收者可否認(rèn)的DE 方案可能更被期望獲得, 也更難設(shè)計[15]. 注意發(fā)送者可否認(rèn)性同樣是有用的, 特別是當(dāng)數(shù)據(jù)擦除在技術(shù)上或法律上不可行的時候. 根據(jù)Nielsen 在2002年給出的不可能結(jié)果[16], 接收者可否認(rèn)DE 方案的私鑰至少需要跟明文一樣長. 為了解決該問題, 目前有兩種方法. 第一種方法是Goldwasser 等人[15]提出的可否認(rèn)編輯(deniable edit), 即限制否認(rèn)后的明文為m′= Edit(m,e), 其中m為原始的明文和e為編輯描述. 從而, 私鑰長度與編輯描述長度|e| 成線性關(guān)系, 獨立于明文的長度|m|. 在許多的應(yīng)用中, 我們只需要否認(rèn)明文m中的部分內(nèi)容, 而不是全部內(nèi)容,使得可否認(rèn)編輯已經(jīng)足夠滿足這些應(yīng)用的需求. 如果定義e=m ⊕m′和Edit(m,e) =m ⊕e=m′, 那么可否認(rèn)編輯方案直接變?yōu)闃?biāo)準(zhǔn)的可否認(rèn)加密方案(盡管失去了效率優(yōu)勢). 因此, 可否認(rèn)編輯可以看作是可否認(rèn)加密的一般化. 第二種方法是預(yù)先計劃的可否認(rèn)加密(plan-ahead deniable encryption)[1,11], 即發(fā)送者/接收者在明文加密之前預(yù)先計劃一定數(shù)量的否認(rèn)明文, 過后只能將密文否認(rèn)為這些預(yù)先計劃的明文. 雖然預(yù)先計劃可否認(rèn)加密方案在否認(rèn)性方面存在一定的限制, 但是該方法允許加密任意多項式長度的明文, 從而支持大型文件的加密. 盡管這兩種方法從不同角度限制了否認(rèn)的能力, 但是他們提供了設(shè)計具體高效可否認(rèn)加密方案的有效途徑.

可否認(rèn)加密可分為公鑰可否認(rèn)加密(發(fā)送者僅知道公鑰, 接收者生成公私鑰) 和私鑰可否認(rèn)加密(發(fā)送者和接收者共享相同的密鑰). 一般而言, 私鑰可否認(rèn)加密比公鑰可否認(rèn)加密更加高效. 然而, 上述大部分不可能結(jié)果不僅適用于公鑰可否認(rèn)加密, 也同樣適用于私鑰可否認(rèn)加密, 使得私鑰可否認(rèn)加密并沒有比公鑰可否認(rèn)加密更容易設(shè)計. 目前, 所有已知的可否認(rèn)加密方案都是從理論上設(shè)計, 沒有考慮其具體效率.本文以設(shè)計具體高效的可否認(rèn)加密方案為主要目標(biāo), 致力于設(shè)計滿足雙方案可否認(rèn)性的私鑰可否認(rèn)加密方案(除非特別說明, 下文提及的可否認(rèn)性均為雙方案可否認(rèn)性).

1.1 本文貢獻(xiàn)

本文首先提出了新的私鑰可否認(rèn)編輯方案, 滿足選擇明文攻擊(CPA) 安全性和接收者可否認(rèn)性, 大幅度降低了Goldwasser 等人[15]方案的密文長度、否認(rèn)密鑰長度(具體的效率比較見1.2 節(jié)). 特別地, 提出的私鑰可否認(rèn)編輯方案降低密文長度超過2|Cedit|κ+3?κ比特, 其中|Cedit| 是關(guān)于編輯函數(shù)Edit 布爾電路表示的AND 門數(shù)量、?=|e| 表示編輯描述長度和κ是安全參數(shù). 而且, 該方案將否認(rèn)密鑰長度從2(?+κ)κ比特降低到僅僅κ比特, 達(dá)到了最優(yōu). 基于Canetti 等人給出的轉(zhuǎn)換技術(shù)[1], 再結(jié)合上“一次一密” 中XOR 操作允許將對隨機數(shù)的編輯傳遞到對明文的編輯, 本文也將提出的滿足接收者可否認(rèn)性的私鑰可否認(rèn)編輯方案轉(zhuǎn)換為發(fā)送者可否認(rèn)的私鑰可否認(rèn)編輯方案.

與Goldwasser 等人[15]給出的私鑰可否認(rèn)編輯方案類似, 本文提出的方案基于單密鑰私鑰函數(shù)加密(single-key secret-key functional encryption, SK2FE) 方案設(shè)計. 本文利用Free-XOR 技術(shù)[17]和半門亂碼電路技術(shù)[18], 再結(jié)合上提出的偽隨機密鑰、標(biāo)簽、密文產(chǎn)生技術(shù), 設(shè)計了新的SK2FE 方案, 滿足特殊加密和解密性質(zhì)(其中該性質(zhì)是設(shè)計私鑰可否認(rèn)編輯方案的特殊安全需求). 與Goldwasser 等人[15]給出的構(gòu)造相比, 本文提出的SK2FE 方案減少了一半以上的密文長度, 也將主密鑰長度從O(nκ) 降低到O(κ) 比特, 同時給出了更加簡單的特殊解密算法, 其中n表示一個輸入的長度. 然后, 基于新的SK2FE方案, 本文設(shè)計了高效的私鑰可否認(rèn)編輯方案.

基于提出的私鑰可否認(rèn)編輯方案, 本文也設(shè)計了新的預(yù)先計劃私鑰接收者可否認(rèn)加密方案, 支持預(yù)先計劃t個否認(rèn)的明文. 該方案適合于加密較長的明文, 當(dāng)t=O(1) 能獲得O(1) 密文率(密文長度/明文長度的比率), 比提出的可否認(rèn)編輯方案有顯著更短的密文. 特別地, 通過混合加密技術(shù), 我們能用可否認(rèn)編輯方案加密O(κ) 比特的密鑰, 然后用私鑰加密方案(即對稱加密方案) 加密任意多項式長度的明文.

1.2 可否認(rèn)加密方案效率與比較

表1 比較了本文的私鑰可否認(rèn)編輯方案與Goldwasser 等人[15]方案的效率, 其中兩個方案都滿足CPA 安全性和接收者可否認(rèn)性. Goldwasser 等人主要從理論上設(shè)計私鑰可否認(rèn)編輯方案, 將接收者可否認(rèn)編輯方案的存在性歸約到單向函數(shù)的存在性. 我們應(yīng)用點置換技術(shù)[19,20]等優(yōu)化方法到Goldwasser 等人的構(gòu)造中, 改進他們方案的計算效率, 然后再與他們的構(gòu)造進行效率比較. 注意點置換技術(shù)的使用沒有引入額外的困難假設(shè), 保證了他們的私鑰可否認(rèn)編輯方案[15]仍然基于單向函數(shù).

表1 私鑰可否認(rèn)編輯加密方案的效率比較(|CSpecial| ＞|CEdit| 和? ≤n)Table 1 Efficiency comparison of secret-key deniable edit schemes (|CSpecial| ＞|CEdit| and ? ≤n)

計算效率的比較僅考慮了否認(rèn)模型下加密算法和解密算法的效率, 忽略了正常模式下相應(yīng)算法的效率比較. 這是因為發(fā)送者和接收者主要在否認(rèn)模式下通信, 很少在正常模式下通信. 對于無需否認(rèn)的加密通信而言, 發(fā)送者和接收者可以利用標(biāo)準(zhǔn)的私鑰加密方案進行通信.

在表1 中的符號說明如下:

·n為明文m的長度,?=|e| 為編輯描述e的長度以及κ為安全參數(shù).

· 布爾電路CEdit用于計算以下函數(shù)FEdit:{0,1}n+?+κ×{0,1}?+κ →{0,1}n:

·|CEdit| 表示布爾電路CEdit中AND 門的數(shù)量;|CSpecial| 表示電路CSpecial中AND 門和XOR 門的數(shù)量, 其中注意Goldwasser 等人[15]沒有考慮Free-XOR 優(yōu)化技術(shù)[17].

·tperm表示計算單個隨機置換π:{0,1}κ →{0,1}κ的運行時間, 其中隨機置換可用密鑰固定的分組密碼實現(xiàn)(比如: AES);tprf表示計算單個偽隨機函數(shù)PRF:{0,1}κ×{0,1}κ →{0,1}κ的運行時間, 其中偽隨機函數(shù)可用分組密碼實現(xiàn). 如果用密鑰固定的AES 實例化隨機置換以及用帶密鑰編排的AES 實例化偽隨機函數(shù), 那么根據(jù)Guo 等人[21]的實驗結(jié)果,tprf≈2tperm.

從表1 可以看到, 本文私鑰可否認(rèn)編輯方案的密文長度比Goldwasser 等人方案[15]減少了超過2|CEdit|κ+3?κ比特. 本文的方案也減少了否認(rèn)密鑰長度2(?+κ) 倍, 使得對于較長的編輯描述e, 能節(jié)省較多的存儲空間. 當(dāng)兩個方案都轉(zhuǎn)化為標(biāo)準(zhǔn)的私鑰可否認(rèn)加密方案時, 本文提出的方案將提供更多的通信和存儲優(yōu)勢, 即減少密文長度2|CEdit|κ+3nκ比特和減少否認(rèn)密鑰長度2nκ比特. 對于私鑰的長度,本文的私鑰可否認(rèn)編輯方案與Goldwasser 等人方案[15]相同, 均與編輯描述的長度成線性關(guān)系. 與否認(rèn)密鑰的長度比較, 私鑰長度是更次要的效率度量. 這是因為發(fā)送者和接收者無需存儲私鑰, 在少數(shù)需要的時候用否認(rèn)密鑰計算得到私鑰即可.

計算效率的比較假設(shè)用AES 實現(xiàn)隨機置換或偽隨機函數(shù), 從而有tprf≈2tperm. 我們主要考慮否認(rèn)模式下加密算法、解密算法和否認(rèn)算法的計算效率比較. 當(dāng)|CSpecial|＞2(n-?) 時, 本文的私鑰可否認(rèn)編輯方案降低解密算法運行時間約(|CSpecial|-2n+2?)tperm. 對于否認(rèn)算法, 當(dāng)|CSpecial|＞2(n+?) 時, 本文的方案降低運行時間約為(|CSpecial|-2n-2?)tperm. 對于加密算法的計算效率, 本文的私鑰可否認(rèn)編輯方案與Goldwasser 等人的方案效率相當(dāng). 在安全性方面, 本文的私鑰可否認(rèn)編輯方案需要基于循環(huán)相關(guān)強健Hash 函數(shù)(circular correlated robust hash function, circular CRHF) 假設(shè)[22], 比Goldwasser 等人方案基于的單向函數(shù)假設(shè)更強.1如果我們將Free-XOR 技術(shù)[17] 和半門亂碼電路技術(shù)[18] 應(yīng)用于優(yōu)化Goldwasser 等人[15] 的可否認(rèn)編輯方案, 那么Goldwasser 等人方案的安全性將依賴于循環(huán)CRHF 假設(shè), 與本文的方案相同. 即便如此, 本文提出的方案仍然顯著減少了密文的長度, 仍然減少否認(rèn)密鑰長度2(?+κ) 倍.

2 預(yù)備知識

2.1 符號

本文用κ表示(計算) 安全參數(shù). 對于n ∈N, 符號[n] 和[0,n] 分別表示集合{1,2,··· ,n}和{0,1,··· ,n}. 對于兩個字符串a(chǎn),b,a‖b表示它們的級聯(lián). 用|x| 表示字符串x的長度. 對于字符串x ∈{0,1}*,xi表示x的第i個比特;以及l(fā)sb(x)表示x的最低比特. 符號x ←S表示從有限集合S中均勻隨機采樣x;x ←D表示根據(jù)分布D采樣x. 縮寫PPT 表示概率多項式時間(probabilistic polynomial time). 本文用negl(·) 表示一個未指定的可忽略函數(shù), 即對于任意的常數(shù)c ≥0, negl(κ) =o(κ-c). 對于(隨機) 算法A,y ←A(x) 表示關(guān)于輸入x運行算法A和獲得輸出y. 用符號y ←A(x;r) 指定算法A所使用的隨機數(shù)r. 為了方便表示, 用{xw}w∈I表示(xw1,xw2,··· ,xwn), 其中wi ∈I對于i ∈[n] 和n是集合I的大小.

對于布爾電路C, 我們可以對電路的每條線進行編號, 使得每條線都有唯一標(biāo)識的索引(假設(shè)從1 開始編號). 電路C由一系列門組成, 每個門有(α,β,γ,T) 形式, 其中α,β是門輸入線索引,γ是門輸出線索引和T ∈{⊕,∧}是門的類型. 本文用I表示電路輸入線索引的集合,O表示電路輸出線索引的集合以及W表示AND 門輸出線索引的集合. 當(dāng)顯示考慮兩個輸入x,y時, 本文用I1和I2分別表示x和y對應(yīng)的電路輸入線索引集合, 滿足I=I1∪I2.

2.2 單密鑰私鑰函數(shù)加密

下面回顧Goldwasser 等人[15]給出的單密鑰私鑰函數(shù)加密(SK2FE) 定義. 特別地, SK2FE 僅保證了弱的安全概念: (1) 敵手至多獲得單個私鑰; (2) 敵手必須在獲得挑戰(zhàn)密文之前選擇私鑰.

定義1 (SK2FE) 針對函數(shù)f:{0,1}n1×{0,1}n2→{0,1}n3(其中n1,n2,n3是安全參數(shù)κ的函數(shù)), 單密鑰私鑰函數(shù)加密方案FE=(Setup,Gen,Enc,Dec) 由以下多項式時間算法組成:

· msk←Setup(1κ): 產(chǎn)生一個主私鑰msk.

· sky ←Gen(msk,y): 輸入主私鑰msk 和y ∈{0,1}n2, 產(chǎn)生一個函數(shù)私鑰sky.

·c ←Enc(msk,x): 輸入主私鑰msk 和x ∈{0,1}n1, 輸出密文c.

·f(x,y)←Dec(sky,c): 輸入函數(shù)私鑰sky和密文c, 輸出消息f(x,y).

正確性. 對于每個安全參數(shù)κ, 消息x ∈{0,1}n1和y ∈{0,1}n2:

單密鑰安全性. 定義在PPT 敵手A和挑戰(zhàn)者之間由比特b ∈{0,1}參數(shù)化的單密鑰私鑰函數(shù)加密安全性實驗FEGamebA(κ) 如下:

(1) 選取msk←Setup(1κ) 和令O(·)=Enc(msk,·) 為加密預(yù)言機(oracle).

(3) 敵手AO(·)(sky) 詢問加密預(yù)言機, 然后輸出一個比特b′, 被作為該實驗的輸出.

我們稱一個單密鑰私鑰函數(shù)加密方案FE=(Setup,Gen,Enc,Dec,SEnc,SDec) 具有特殊加密功能, 如果對于任意PPT 敵手A以下成立:

定義3 我們稱單密鑰私鑰函數(shù)加密方案FE = (Setup,Gen,Enc,Dec,SEnc,SDec) 具有特殊解密功能, 如果對于每個安全參數(shù)κ和消息x ∈{0,1}n1:

2.3 偽隨機函數(shù)和私鑰加密方案

下面回顧偽隨機函數(shù)的標(biāo)準(zhǔn)定義以及私鑰加密方案(也稱為對稱加密方案) 的CPA 安全性. 此外, 我們也要求私鑰加密方案滿足一次偽隨機性, 即要求挑戰(zhàn)密文與密文空間中的隨機值不可區(qū)分.

定義4 (偽隨機函數(shù)) 令PRF :{0,1}κ×{0,1}κ →{0,1}κ是有效的密鑰函數(shù). 我們稱PRF 是一個偽隨機函數(shù), 如果對于任意PPT 區(qū)分器A, 滿足以下成立:

其中sk←{0,1}κ被均勻隨機選取和fκ是從{0,1}κ映射到{0,1}κ的函數(shù)集合中均勻隨機選取.

定義5 (私鑰加密方案) 一個私鑰加密方案SE=(Gen,Enc,Dec) 由以下多項式時間算法組成:

· sk←Gen(1κ): 產(chǎn)生一個私鑰sk.

·c ←Enc(sk,m): 輸入私鑰sk 和明文m ∈{0,1}n, 輸出密文c.

3 高效的單密鑰私鑰函數(shù)加密方案

本節(jié)首先給出亂碼電路(garbled circuits) 的定義并描述相應(yīng)的半門構(gòu)造, 然后提出新的單密鑰私鑰函數(shù)加密方案, 最后證明該方案的安全性.

3.1 亂碼電路方案及其半門構(gòu)造

下面回顧Bellare 等人[23]給出的亂碼電路定義. 為了便于描述本文提出的SK2FE 構(gòu)造, 本文擴展他們的定義, 使得顯示考慮兩個不同的輸入x和y. 本文給出的定義保證輸入x的機密性, 即使允許敵手決定輸入y對應(yīng)的編碼(也稱為標(biāo)簽). 該擴展的定義使得我們能在不依賴于隨機預(yù)言機(random oracle,RO) 的假設(shè)下設(shè)計高效的單密鑰私鑰函數(shù)加密方案.

定義6 (亂碼電路方案) 對于任意布爾電路C:{0,1}n1×{0,1}n2→{0,1}n3, 亂碼電路方案GC =(Garble,Encode,Eval,Decode) 定義如下:

· (?C,e,d)←Garble(1κ,C): 輸入布爾電路C, 輸出亂碼電路?C和解碼信息d.

· (X,Y)←Encode(e,x,y): 輸入編碼信息e以及x ∈{0,1}n1、y ∈{0,1}n2, 輸出x對應(yīng)的編碼X以及y對應(yīng)的編碼Y.

·Z ←Eval(?C,(X,Y)): 輸入亂碼電路?C和電路輸入線編碼(X,Y), 輸出電路輸出線的編碼Z.

·z ←Decode(d,Z): 輸入解碼信息d和電路輸出線編碼Z, 輸出z ∈{0,1}n3.

正確性. 對于每個安全參數(shù)κ ∈N、布爾電路C:{0,1}n1×{0,1}n2→{0,1}n3以及輸入x ∈{0,1}n1,y ∈{0,1}n2, 以下成立:

圖1 半門亂碼電路方案Figure 1 Half-gates garbling scheme

從經(jīng)典的亂碼電路半門構(gòu)造, 我們?nèi)菀妆ＷC方案1 的正確性. 根據(jù)文獻(xiàn)[18] 給出的安全證明, 我們能在循環(huán)相關(guān)強健性假設(shè)[21,22]下保證方案1 滿足不可區(qū)分安全性. 注意輸入x和y的編碼是獨立的,從而即使敵手能選擇y的編碼Y, 但是也不能區(qū)分X0與X1. 最近, Rosulek 和Roy[24]突破了半門構(gòu)造的下界, 提出了通信更低的亂碼電路方案, 使得每個AND 門僅需1.5κ+5 比特通信(其中半門構(gòu)造需要每個AND 門2κ比特通信), 當(dāng)要求比半門構(gòu)造50% 更多的CRHF 函數(shù)計算. 我們也能擴展Rosulek 和Roy的亂碼電路構(gòu)造從單個輸入到兩個不同的輸入, 然后應(yīng)用到本文的單密鑰私鑰函數(shù)加密方案(見3.2 節(jié))中, 以獲得更短的密文長度. 本文留具體的構(gòu)造細(xì)節(jié)作為未來的研究工作.

3.2 單密鑰私鑰函數(shù)加密構(gòu)造

3.3 安全性證明

正常解密算法根據(jù)比特yw(w ∈I2) 的取值恢復(fù)標(biāo)簽集合Y, 再結(jié)合密文中的X執(zhí)行亂碼電路運算,最后用解碼信息d解碼得到函數(shù)輸出f(x,y). 從而, 根據(jù)正常加解密算法的描述, 正常解密算法的正確性容易獲得. 對于特殊解密算法, 該算法執(zhí)行與正常加密算法相同的運算得到L0w(w ∈I1), 然后與X中的標(biāo)簽Lxww比對得到輸入x的每個比特. 因此, 根據(jù)正常加密算法和特殊解密算法的描述, 特殊解密算法的正確性容易保證. 下面, 本文證明私鑰函數(shù)加密方案FE 的單密鑰安全性和特殊加密安全性.

定理1 如果GC 是滿足不可區(qū)分性的亂碼電路方案以及PRF 是安全的偽隨機函數(shù), 那么如圖2 所示的私鑰函數(shù)加密方案FE 滿足單密鑰安全性和特殊加密安全性. 特別地, 以下關(guān)系成立:

圖2 單密鑰私鑰函數(shù)加密構(gòu)造Figure 2 Construction of single-key secret-key functional-encryption

證明: 本文首先證明方案FE 滿足單密鑰安全性. 該證明通過一系列游戲G0,G1,··· ,G4執(zhí)行, 其中用Pr[Gi] 表示敵手在Gi中輸出1 的概率. 本文在圖3 中描述了這些游戲, 其中方框標(biāo)出的內(nèi)容表示該游戲相較于上一個游戲所做的改變. 本文將證明任意兩個連續(xù)的游戲是不可區(qū)分的.

圖3 關(guān)于我們私鑰函數(shù)加密方案的單密鑰安全性的系列游戲Figure 3 Sequence of games for single-key security of proposed secret-key functional-encryption scheme

游戲G1: 該游戲與G0相同, 除了如果一旦發(fā)現(xiàn)O(·)=FE.Enc(msk,·) 產(chǎn)生的所有密文和挑戰(zhàn)密文c*中存在相同的隨機數(shù)r, 那么游戲直接中止.

根據(jù)以上證明, 我們?nèi)菀鬃C明私鑰函數(shù)加密方案FE 滿足特殊加密安全性. 特別地, 重用游戲G1到G5,我們能將加密預(yù)言機從O(·)=Enc(msk,·) 逐步跳轉(zhuǎn)到O(·)=Enc(sky,·). 從而, 容易獲得以下的界:

以上的安全界使得本文完成該證明.

4 高效的私鑰可否認(rèn)編輯方案

基于提出的單密鑰私鑰函數(shù)加密方案, 本節(jié)描述高效的私鑰可否認(rèn)編輯方案, 滿足CPA 安全性和接收者可否認(rèn)性. 此外, 本文也轉(zhuǎn)化該接收者可否認(rèn)編輯方案為發(fā)送者可否認(rèn)編輯方案, 但需要額外一輪的交互. 在此之前, 本文首先回顧接收者私鑰可否認(rèn)編輯方案的定義.

4.1 私鑰可否認(rèn)編輯定義

Goldwasser 等人[15]給出了滿足雙方案接收者可否認(rèn)性的編輯方案定義. 本文擴展他們的定義從支持否認(rèn)私鑰到更強的否認(rèn)密鑰生成隨機數(shù)如下:

定義7 (私鑰可否認(rèn)編輯) 令消息長度n和編輯描述長度?均為安全參數(shù)κ的多項式函數(shù). 令Edit:{0,1}n×{0,1}? →{0,1}n為多項式時間的編輯函數(shù). 一個私鑰可否認(rèn)編輯方案DE = (Gen,Enc,Dec,DenGen,DenEnc,DenDec,Deny) 由以下多項式時間算法組成:

· (Gen,Enc,Dec) 滿足定義5 中描述的私鑰加密方案定義.

· dk←DenGen(1κ): 否認(rèn)密鑰生成算法產(chǎn)生一個否認(rèn)密鑰dk.

·c ←DenEnc(dk,m): 否認(rèn)加密算法輸入否認(rèn)密鑰dk 和明文m ∈{0,1}n, 輸出可否認(rèn)密文c.

·m ←DenDec(dk,c): 否認(rèn)解密算法輸入密鑰dk 和密文c, 輸出明文m.

如果定義編輯描述e=m ⊕m′和Edit(m,e)=m ⊕e=m′, 那么可否認(rèn)編輯方案直接是標(biāo)準(zhǔn)的可否認(rèn)加密方案. 在此情況下,?=n成立. 從而, 可否認(rèn)編輯可以看作是可否認(rèn)加密的一般化概念.

4.2 具體構(gòu)造

基于提出的單密鑰私鑰函數(shù)加密方案FE = (Setup,Gen,Enc,Dec,SEnc,SDec), 本文設(shè)計了高效的接收者可否認(rèn)編輯方案DE. 該方案基本與Goldwasser 等人[15]給出的方案相同, 除了以下3 點不同:

· 本文的方案基于提出的更高效單密鑰私鑰函數(shù)加密方案(見3.2 節(jié)) 設(shè)計, 使得該方案比Goldwasser 等人給出的私鑰可否認(rèn)編輯方案更加有效.

· 本文的方案支持更強的隨機數(shù)否認(rèn)(代替私鑰否認(rèn)), 并簡化了正常模式下密鑰生成算法.

· 與Goldwasser 等人方案相同,加密算法仍然加密(m,k),其中m ∈{0,1}n為明文和k ∈{0,1}κ+?為隨機數(shù). 然而, 對于否認(rèn)模式下的解密算法, 本文的方案只用FE 的特殊解密算法SDec 解密密文恢復(fù)明文m(而不是(m,k)). 該簡單的優(yōu)化不能提升Goldwasser 等人方案的效率, 但是能夠減少本文方案的解密算法計算時間(?+κ)tprf.

為了能否認(rèn)隨機數(shù)(而不是私鑰), 本文要求SK2FE 方案FE 滿足以下性質(zhì):

· 不失一般性, 函數(shù)密鑰sky ←FE.Gen(msk,y) 總是分解為sky=(y,sk′y).

· 令Ky為y ∈{0,1}n2所對應(yīng)的密鑰空間. 存在PPT 采樣算法Sample 能從Ky中均勻隨機選取sk′y. 為了描述簡單, 本文也用sk′y ←Ky表示從密鑰空間Ky中均勻隨機選取sk′y.

· 存在逆采樣算法IGen滿足: 對于任意的y ∈{0,1}n2和sky ←FE.Gen(msk,y),r ←IGen(sk′y) 使得sk′y=Sample(r) 且r與均勻的隨機數(shù)計算不可區(qū)分, 其中sky=(y,sk′y).

第3 節(jié)給出的SK2FE 方案滿足以上性質(zhì). 具體地, 密鑰空間Ky={0,1}n2κ; Sample 隨機選取sk′i,yi ←

其中m ∈{0,1}n和k ∈{0,1}κ+?.

給定關(guān)于函數(shù)FEdit具有特殊加解密功能的單密鑰私鑰函數(shù)加密方案FE, 本文獲得以下高效的私鑰可否認(rèn)編輯方案.

方案3 (私鑰可否認(rèn)編輯) 令消息長度n和編輯描述長度?均為安全參數(shù)κ的函數(shù). 對于任意多項式時間的編輯函數(shù)Edit :{0,1}n×{0,1}? →{0,1}n, 本文能構(gòu)造一個私鑰可否認(rèn)編輯方案DE =(Gen,Enc,Dec,DenGen,DenEnc,DenDec,Deny), 如圖4 所示.

圖4 私鑰可否認(rèn)編輯加密方案構(gòu)造Figure 4 Construction of proposed secret-key deniable edit encryption scheme

對于否認(rèn)模式下的算法, 本文的私鑰可否認(rèn)編輯方案能獲得完美的正確性, 基于底層SK2FE 方案FE的完美正確性. 對于正常模式下的算法, 本文的方案獲得統(tǒng)計正確性, 即正確性以概率1-1/2κ成立. 特別地, 因為y,k ∈{0,1}κ+?都是均勻隨機的字符串, 所以事件?es.t.y ⊕k= (0κ,e) 發(fā)生的概率至多為1/2κ. 如果該事件沒有發(fā)生, 那么解密算法將正確恢復(fù)明文m, 基于SK2FE 方案FE 的完美正確性.

定理2 如果FE 是關(guān)于函數(shù)FEdit的滿足特殊加解密性質(zhì)的單密鑰私鑰函數(shù)加密方案(即滿足定義1),那么如圖4 所示的私鑰可否認(rèn)編輯方案DE 滿足選擇明文安全性和接收者編輯可否認(rèn)性. 特別地, 以下關(guān)系成立:

為了否認(rèn)t個密文c= (c1,c2,··· ,ct)(其中ci是(mi,ki) 的FE 密文), 本文能首先產(chǎn)生關(guān)于向量y的FE 私鑰sky(其中yi=ki ⊕(0κ,ei)), 然后用算法IGen計算得到密鑰生成的隨機數(shù)rc,e.

4.3 發(fā)送者可否認(rèn)編輯方案

本節(jié)將4.2 節(jié)描述的接收者可否認(rèn)編輯方案DE 轉(zhuǎn)化為發(fā)送者可否認(rèn)編輯方案DE′, 其中轉(zhuǎn)化后的方案如圖5 所示. 當(dāng)方案DE 是非交互的, 轉(zhuǎn)化后的方案DE′是交互的.

圖5 發(fā)送者可否認(rèn)編輯方案Figure 5 Sender-deniable edit scheme

本文主要基于Canetti 等人[1]給出的接收者可否認(rèn)加密方案與發(fā)送者可否認(rèn)加密方案之間的轉(zhuǎn)換方法, 也觀察到“一次一密” 中XOR 操作允許將對隨機數(shù)的編輯轉(zhuǎn)換到對明文的編輯. 具體地, 如圖5 所示的發(fā)送者可否認(rèn)編輯方案DE′設(shè)計思想如下:

· 發(fā)送者能用DE.DenGen 和DE.Gen 生成否認(rèn)私鑰dk 和正常私鑰sk, 并與接收者共享這些私鑰.然后, 接收者用加密算法加密一個隨機數(shù)s并發(fā)送相應(yīng)的密文c1給發(fā)送者; 發(fā)送者能用對應(yīng)的解密算法解密c1獲得s. 發(fā)送者能通過“一次一密” 的方法用s加密真正的明文m得到密文c2. 在收到密文c2以后, 接收者能用s解密密文c2獲得明文m.

· 因為明文m和隨機數(shù)s處于對稱關(guān)系, 所以能通過否認(rèn)s來實現(xiàn)對明文m的否認(rèn). 具體地, 令s′=Edit(s,e), 那么c2⊕s′=(m ⊕s)⊕s′=Edit(m,e). 這是因為通過編輯函數(shù)Edit 對隨機數(shù)s任意比特的翻轉(zhuǎn), 都將記錄在s′中, 使得s ⊕s′在相應(yīng)翻轉(zhuǎn)位置比特為1, 進而翻轉(zhuǎn)m相應(yīng)位置的比特, 從而實現(xiàn)對m的編輯. 更具體來說, 在可否認(rèn)模式下, 發(fā)送者能用算法DE.Deny(dk,c1,e)計算否認(rèn)的隨機數(shù)rc,e, 使得Edit(s,e) = DE.Dec(skc,e,c1), 其中skc,e ←DE.Gen(1κ;rc,e). 進一步有c2⊕Edit(s,e)=m ⊕s ⊕Edit(s,e)=Edit(m,e) 成立.

因為“一次一密” 是信息論安全的, 所以如圖5 所示的發(fā)送者可否認(rèn)編輯方案的安全性完全依賴于底層接收者可否認(rèn)編輯方案的安全性.

5 預(yù)先計劃的可否認(rèn)加密方案

本節(jié)基于第4 節(jié)提出的私鑰可否認(rèn)編輯方案設(shè)計預(yù)先計劃的可否認(rèn)加密方案. 本文僅描述滿足接收者可否認(rèn)性的預(yù)先計劃可否認(rèn)加密方案, 其中滿足發(fā)送者可否認(rèn)性的方案能利用Canetti 等人[1]給出的轉(zhuǎn)換方法獲得(見第4.3 節(jié)). 本文主要借鑒了O’Neill 等人[11]提出的方法, 根據(jù)私鑰可否認(rèn)加密的特點優(yōu)化了該方法, 使得否認(rèn)密文無需存儲加密所用的隨機數(shù). 優(yōu)化后的方法也很好地適配了底層所用的私鑰可否認(rèn)編輯方案. 在給出具體構(gòu)造之前, 本文首先給出預(yù)先計劃私鑰可否認(rèn)加密方案的定義.

5.1 預(yù)先計劃私鑰可否認(rèn)加密的定義

以下滿足接收者可否認(rèn)性的預(yù)先計劃私鑰加密方案的定義是通過修改O’Neill 等人[11]給出的滿足雙可否認(rèn)性的預(yù)先計劃公鑰加密方案的定義獲得. 本文給出的定義也擴展了O’Neill 等人給出的定義, 從預(yù)先計劃1 個否認(rèn)明文到預(yù)先計劃t個否認(rèn)明文, 其中t ∈N,t ≥1.

定義9 (預(yù)先計劃的私鑰可否認(rèn)加密) 令明文長度n和預(yù)先計劃否認(rèn)明文的數(shù)量t均為安全參數(shù)κ的多項式函數(shù). 對于預(yù)先計劃t個否認(rèn)明文的私鑰可否認(rèn)加密方案PADE = (Gen,Enc,Dec,DenGen,DenEnc,DenDec,Deny) 由以下多項式時間算法組成:

· (Gen,Enc,Dec) 滿足定義5 中描述的私鑰加密方案定義.

· dk←DenGen(1κ): 否認(rèn)密鑰生成算法產(chǎn)生一個否認(rèn)密鑰dk.

· ct←DenEnc(dk,m,{mi}i∈[t]): 否認(rèn)加密算法輸入否認(rèn)密鑰dk、真實的明文m ∈{0,1}n和t個預(yù)先計劃的否認(rèn)明文m1,m2,··· ,mt ∈{0,1}n, 輸出可否認(rèn)的密文ct.

·m ←DenDec(dk,ct): 否認(rèn)解密算法輸入密鑰dk 和密文ct, 輸出明文m.

·rct,q ←Deny(dk,ct,q): 否認(rèn)算法輸入否認(rèn)密鑰dk、密文ct 和否認(rèn)明文的索引q ∈[t], 輸出隨機數(shù)rct,q滿足: skct,q ←Gen(1κ;rct,q) 和mq=Dec(skct,q,ct).

正確性. 對于每個安全參數(shù)κ ∈N、真實明文m ∈{0,1}n和否認(rèn)明文m1,m2,··· ,mt ∈{0,1}n, 以下成立:

選擇明文安全性. 私鑰加密方案(Gen,Enc,Dec) 和(DenGen,DenEnc,DenDec) 分別滿足定義5 中給出的選擇明文攻擊(CPA) 安全性. 令PADEnorm= (Gen,Enc,Dec) 和PADEdeny= (DenGen,DenEnc,

5.2 預(yù)先計劃的私鑰可否認(rèn)加密構(gòu)造

本節(jié)給出預(yù)先計劃私鑰可否認(rèn)加密方案的具體構(gòu)造如下.

方案4 (預(yù)先計劃私鑰可否認(rèn)加密) 令Edit′為以下編輯函數(shù):

給定關(guān)于以上編輯函數(shù)Edit′的私鑰接收者可否認(rèn)編輯方案DE = (Gen,Enc,Dec,DenGen,DenEnc,DenDec,Deny) 和私鑰加密方案SE = (Gen,Enc,Dec), 本文設(shè)計的預(yù)先計劃接收者可否認(rèn)加密方案PADE = (Gen,Enc,Dec,DenGen,DenEnc,DenDec,Deny) 如圖6 所示. 方案PADE 主要采用混合加密的思想, 用私鑰可否認(rèn)編輯方案DE 加密隨機的密鑰, 然后用這些密鑰和私鑰加密方案SE 加密明文. 加密算法中的隨機值p用于將真實的密文c0插入在隨機的位置, 使得敵手無法判斷哪個密文加密了真實的明文, 從而支持了對密文的否認(rèn). 通過底層可否認(rèn)編輯方案和私鑰加密方案的正確性, 該預(yù)先計劃可否認(rèn)加密方案的正確性是直接的, 其中解密算法總是用K0解密對應(yīng)的密文c′p.

在圖6 所示的預(yù)先計劃可否認(rèn)加密方案中, PADE.DenEnc 算法選取了一個隨機數(shù)k ∈{0,1}κ并將其加密. 直觀上看, 這似乎是不必要的. 然而, 為了在私鑰場景下達(dá)到可證明安全性, 本文需要用隨機數(shù)k區(qū)分挑戰(zhàn)密文ct 和其他密文. 具體而言, 敵手獲得隨機數(shù)rct,q后, 可執(zhí)行密鑰生成算法PADE.Gen(1κ,rct,q) 獲得私鑰skct,q. 根據(jù)編輯描述e= (k,p)⊕(0κ,q) 和編輯函數(shù)Edit′的定義, 容易看到PADE.Dec(skct,q,ct)=mq. 對于任意的其他密文ct′, PADE.Dec(skct,q,ct′) 計算得到真實的明文m, 除非密文ct 和ct′用的隨機數(shù)k相同, 其發(fā)生的概率至多為1/2κ. 在這種情況下, 敵手即使獲得密鑰生成的隨機數(shù)以后, 也不能區(qū)分在正常模式和否認(rèn)模式下加密預(yù)言機的不同加密方式.

其中qo表示敵手A詢問加密預(yù)言機的數(shù)量.

兩個私鑰加密方案PADEnorm= (Gen,Enc,Dec) 和PADEdeny= (DenGen,DenEnc,DenDec) 的CPA安全性可以直接由底層可否認(rèn)編輯方案DEnorm和DEdeny的CPA 安全性以及私鑰加密方案SE 的CPA安全性保證. 在安全證明上主要的不同是: PADEdeny需要利用混合論證(hybrid argument) 方法一步一步將密文c0,c1,··· ,ct中的明文替換為另一個明文; 而PADEnorm并不需要混合論證, 由于c1,c2,··· ,ct是隨機的密文. 方案PADE 的預(yù)先計劃接收者可否認(rèn)性可以直接由底層可否認(rèn)編輯方案DE 的接收者編輯可否認(rèn)性和私鑰加密方案SE 的一次偽隨機性保證, 其中基于SE 的一次偽隨機性利用混合論證方法將除mq之外其他明文對應(yīng)的密文替換為均勻隨機的密文. 具體而言, 以上定理的證明描述如下:

基于以上游戲之間的界, 敵手A針對PADEdeny選擇明文安全性的優(yōu)勢被界定如下:

通信與存儲效率分析. 本文用第4 節(jié)描述的私鑰可否認(rèn)編輯方案實例化方案DE. 對于私鑰加密方案SE, 本文用偽隨機函數(shù)PRF:{0,1}κ×{0,1}κ →{0,1}n實現(xiàn). 特別地,

在本文的預(yù)先計劃私鑰可否認(rèn)加密方案中密鑰K0,K1,··· ,Kt都是獨立均勻隨機的且僅使用一次. 從而, 一次性加密t+ 1 個n比特長的明文僅需(t+ 1)n比特的密文. 該函數(shù)PRF 容易從偽隨機置換PRF′:{0,1}κ×{0,1}κ →{0,1}κ, 即PRF(K,r) = PRF′(K,r‖1)‖···‖PRF′(K,r‖?), 其中r ∈[0,t] 和?=「n/.

預(yù)先計劃私鑰可否認(rèn)加密方案PADE 的否認(rèn)密鑰長度和私鑰長度分別為|dk| =κ比特和|sk| =(logt+κ)κ比特. 下面分析方案PADE 的密文長度. 令以下函數(shù)FEdit′為編輯函數(shù)Edit′對應(yīng)的函數(shù):

其中m ∈ {0,1}n. 對于較大的明文(即n= poly(κ) 較大) 和預(yù)先計劃的否認(rèn)明文數(shù)量較少(即t=O(1)), 那么方案PADE 的密文長度比方案DE 的密文長度非常更短. 當(dāng)t=O(1) 和n?|CEdit′|κ時, 本文的方案能獲得O(1) 的密文率.