基于非完美隨機(jī)源的密碼學(xué)原語(yǔ)的安全性研究綜述

姚燕青,李舟軍

?

基于非完美隨機(jī)源的密碼學(xué)原語(yǔ)的安全性研究綜述

姚燕青,李舟軍

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院 北京 中國(guó) 100191

密碼學(xué)是信息安全的核心研究?jī)?nèi)容。傳統(tǒng)的密碼學(xué)原語(yǔ)理想地假設(shè)秘密服從均勻隨機(jī)分布。然而, 在現(xiàn)實(shí)世界中往往并非如此。例如, 若秘密源為生物數(shù)據(jù)、物理源、部分泄漏的秘密等時(shí), 相應(yīng)的分布并不服從均勻分布。這樣的一些分布構(gòu)成的集合稱為“非完美隨機(jī)源”。因此, 基于非完美隨機(jī)源的密碼學(xué)原語(yǔ)是否仍具有安全性？這已成為當(dāng)今密碼學(xué)前沿研究領(lǐng)域的熱點(diǎn)和難點(diǎn)課題之一。本文闡述了基于非完美隨機(jī)源的密碼學(xué)原語(yǔ)的研究背景、意義及發(fā)展歷程, 重點(diǎn)介紹了該領(lǐng)域的最新進(jìn)展, 即Dodis和Yao[CRYPTO 2015]發(fā)現(xiàn)的基于一般的非完美隨機(jī)源的傳統(tǒng)隱私(包括位抽取器、加密、承諾、秘密分享方案)和差分隱私的(不)可能性結(jié)果。最后, 指出了當(dāng)前該領(lǐng)域值得探索的問(wèn)題。

非完美隨機(jī)源; 密碼學(xué)原語(yǔ); 安全性; 傳統(tǒng)隱私; 差分隱私

1 引言

密碼學(xué)是網(wǎng)絡(luò)信息安全的理論基礎(chǔ)和必要保證。密碼系統(tǒng)的輸出必須在敵手看來(lái)是一系列的隨機(jī)值, 看起來(lái)與原始信息毫無(wú)關(guān)聯(lián)。在設(shè)計(jì)密碼系統(tǒng)時(shí), 密鑰必須為隨機(jī)的, 否則破解密文將不再困難。密碼學(xué)中著名的Kerckhoff準(zhǔn)則為: “一個(gè)密碼系統(tǒng)的安全性都應(yīng)該基于密鑰的安全性, 而不是基于算法的細(xì)節(jié)的安全性”。可見(jiàn), 密鑰的隨機(jī)性在密碼系統(tǒng)中起著極其關(guān)鍵的作用。在公鑰加密體制中, 為了達(dá)到選擇明文攻擊下的不可區(qū)分性(簡(jiǎn)稱為IND-CPA), 除了要求公鑰和明文在敵手看來(lái)是隨機(jī)的, 每次加密中還需引入新鮮獨(dú)立的隨機(jī)串。因此, 隨機(jī)性在某種程度上決定了密碼系統(tǒng)的安全性。

在傳統(tǒng)的密碼學(xué)研究中, 假設(shè)秘密服從均勻隨機(jī)分布。密碼應(yīng)用大多適用算法來(lái)生成隨機(jī)數(shù)。這些算法是確定的, 所以產(chǎn)生的序列并非統(tǒng)計(jì)隨機(jī)的。但當(dāng)算法好時(shí), 產(chǎn)生的序列可以經(jīng)受住隨機(jī)性檢測(cè)。這樣的數(shù)稱為偽隨機(jī)數(shù)。然而在諸多現(xiàn)實(shí)應(yīng)用中, 秘密連偽隨機(jī)的要求都達(dá)不到。例如: 若秘密源為生物數(shù)據(jù)[6,21]、物理源[8,11]、部分泄漏的秘密[3,40]、Diffie- Hellman密鑰交換中的群元素[26,31]時(shí), 則它不是完美隨機(jī)的。相應(yīng)的分布不服從均勻分布。一些非均勻分布構(gòu)成的集合稱為“非完美隨機(jī)源(Imperfect Random Source)”。例如, 多數(shù)已有的安全模型假設(shè)在加密過(guò)程中不會(huì)泄漏關(guān)于密鑰和用于加密的隨機(jī)值的信息, 而真實(shí)環(huán)境中敵手可能會(huì)通過(guò)各種密鑰泄漏攻擊(例如計(jì)算時(shí)間、功耗、故障檢測(cè)、電磁輻射、散熱等)來(lái)獲得關(guān)于秘密狀態(tài)的部分信息。又如, 有些機(jī)構(gòu)利用生物特征來(lái)提取密鑰, 由于生物特征(例如指紋、臉相、虹膜等)的唯一性和終身不變性, 用這種特征來(lái)提取密鑰具有不被遺忘或丟失, 隨身可用, 不易被偽造等優(yōu)點(diǎn), 不過(guò)這樣的密鑰亦不服從均勻分布。

密碼學(xué)原語(yǔ)是密碼系統(tǒng)的基本構(gòu)件。密碼學(xué)原語(yǔ)包括: 哈希函數(shù)、消息認(rèn)證碼、簽名方案、抽取器、加密方案、承諾、秘密分享、差分隱私、密鑰生成函數(shù)、偽隨機(jī)數(shù)生成器等。當(dāng)今密碼學(xué)領(lǐng)域的一個(gè)研究熱點(diǎn)和難點(diǎn)課題是: 原有的密碼學(xué)原語(yǔ)在非完美隨機(jī)源下是否仍然具有安全性？該領(lǐng)域的研究在秘密取自物理源、生物源、部分泄漏或篡改的秘密源的現(xiàn)實(shí)社會(huì)中具有廣闊的應(yīng)用前景。

1.1 國(guó)內(nèi)外的相關(guān)研究團(tuán)隊(duì)

目前, 國(guó)際上已有一些著名研究團(tuán)隊(duì)研究基于非完美隨機(jī)源的密碼學(xué), 如: 美國(guó)麻省理工學(xué)院的圖靈獎(jiǎng)獲得者Shafi Goldwasser教授[7]的研究小組、哈佛大學(xué)的Vadhan和Sudan教授[14,17]的研究小組、美國(guó)紐約大學(xué)的Yevgeniy Dodis教授[5,17,20]的研究小組、美國(guó)University of Texasat Austin的David Zuckerman教授[32,46]的研究小組、以色列Weizmann Institute of Science的Moni Naor教授[4]的研究小組、澳大利亞伍倫貢大學(xué)的Yi Mu教授[15]的研究小組等?；诜峭昝离S機(jī)源的密碼體制(尤其是泄漏容忍的密碼體制)也引起了國(guó)內(nèi)一些機(jī)構(gòu)的研究興趣, 如中科院信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室[36,47]、清華大學(xué)[30]、上海交通大學(xué)[25,33]、武漢大學(xué)[22]、暨南大學(xué)[35]、山東大學(xué)[29]等。

到目前為止, 學(xué)者們已得到關(guān)于該課題的一些結(jié)果。概括來(lái)講, 認(rèn)證方案(例如消息認(rèn)證碼、數(shù)字簽名方案)對(duì)于密鑰的隨機(jī)性程度的要求較為寬松[1,20,16,38], 但加密方案以及其他涉及“隱私”的方案卻并非如此(例如, 文獻(xiàn)[1,5,20,23,37,41])。本文將論述幾種典型的非完美隨機(jī)源, 然后分別闡述基于非完美隨機(jī)源的認(rèn)證方案、傳統(tǒng)隱私體制、差分隱私體制的安全性研究的發(fā)展歷程及發(fā)展動(dòng)態(tài), 其中將重點(diǎn)介紹 Dodis和Yao 在 CRYPTO 2015 中的最新結(jié)果, 接著介紹計(jì)算理論意義下基于弱隨機(jī)密鑰的密碼學(xué)原語(yǔ)的安全性研究歷程及存在的問(wèn)題。最后, 指出該領(lǐng)域目前值得探索的問(wèn)題。

2 非完美隨機(jī)源模型

目前, 已出現(xiàn)了一些形式化的模型(例如弱源、Block源、Santha-Vazirani源、偏差控制受限源)來(lái)抽象非完美隨機(jī)源[2,10,12,13,19,34,41,42,46]。粗略地說(shuō), 它們分為可抽取的和不可抽取的。位抽取問(wèn)題可概括如下: 該問(wèn)題有三個(gè)參數(shù),, 和。用戶選取函數(shù), 敵手選取個(gè)輸入位中的個(gè)位, 并對(duì)這個(gè)位的取值進(jìn)行固定, 用戶不知道敵手選了哪個(gè)位以及這個(gè)位的取值是多少。剩余的個(gè)輸入位的取值為獨(dú)立無(wú)偏的拋幣游戲的輸出。用戶用函數(shù)作用于這位輸入。用戶的目標(biāo)是使得函數(shù)的輸出服從上的均勻分布, 而敵手的目標(biāo)則是使得函數(shù)的輸出分布是有偏的。位抽取問(wèn)題歸結(jié)為用戶的取勝問(wèn)題。文獻(xiàn)[12]給出了使敵手失敗的的上下界。概括地講, 可抽取的源(例如文獻(xiàn)[10,12,34,42])允許幾乎均勻分布的確定性抽取。盡管使得抽取比率和效率最優(yōu)化是很有趣的問(wèn)題, 但從質(zhì)的角度, 適用于完美隨機(jī)源的應(yīng)用中的源都可用可抽取的源來(lái)代替。不幸的是, 人們很快意識(shí)到現(xiàn)實(shí)中的許多源不是可抽取的(例如弱源、Block源、Santha-Vazirani源、偏差控制受限源)[13,19,41]。

Santha-Vazirani 源 Santha和Vazirani于1986年提出了Santha-Vazirani源[41](簡(jiǎn)記為SV源)。該源產(chǎn)生一系列的位12,, 滿足這里為任意正整數(shù)。可高效取樣的SV源[1]是逐位產(chǎn)生的, 對(duì)于產(chǎn)生的位r, 敵手在獲悉已產(chǎn)生的1 個(gè)位12, …, r的信息的前提下, 以“在線”的方式高效地對(duì)服從均勻分布的r以獨(dú)立概率進(jìn)行篡改。不難看出, 在均勻隨機(jī)的位二元串上進(jìn)行上述篡改得到的隨機(jī)變量服從的SV分布。事實(shí)上, 任何SV源既可看成物理源, 又可看成由敵手對(duì)均勻隨機(jī)的位二元串進(jìn)行上述篡改而得到的源[1]。不管有多少個(gè)SV位, 均不存在1位的確定性抽取器, 能夠從SV源中抽取出偏差嚴(yán)格小于的1位[41]。

偏差控制受限源在現(xiàn)實(shí)世界中, 流源產(chǎn)生的每一位可能不是均勻隨機(jī)的, 由于噪音、測(cè)量錯(cuò)誤及其它一些缺陷, 微小的錯(cuò)誤是不可避免的; 由于內(nèi)部聯(lián)系、測(cè)量條件限制或設(shè)置不當(dāng), 一些位非平凡地依賴于前面的位, 其極端情況是有的位由前面的位完全確定。2001年, Dodis[19]給出了對(duì)上述源的模型化表示, 稱之為偏差控制受限源(簡(jiǎn)稱為 BCL 源)。該源產(chǎn)生一系列的位12 ,…, x: 對(duì)12來(lái)說(shuō),x的值按以下兩種方式之一依賴于12,x:

(A)x由12 ,…, x完全確定, 但這種情況發(fā)生的次數(shù)至多為某常數(shù);

弱源和Block源 最小熵至少為的-位弱源(Weak Source) 定義為集合Block源作為弱源的推廣, 允許有個(gè)塊1,…,R, 每塊在假設(shè)已知前面的塊的前提下有新鮮的位熵。與SV源相比, Block源不含最大熵的信息, 從這個(gè)意義上來(lái)說(shuō), Block源的限制性更少, 也比SV源更切合實(shí)際。

3 基于非完美隨機(jī)源的概率多項(xiàng)式時(shí)間的算法和認(rèn)證研究

盡管不可抽取的源排除了對(duì)于所有應(yīng)用來(lái)說(shuō)從非完美源到完美源的“黑盒編譯”, 但我們?nèi)韵Ｍ囟ǖ牟豢沙槿〉脑醋阋赃m用于模擬概率算法及密碼學(xué)中的某些應(yīng)用。一系列結(jié)果[2,13,41,43,46]表明: 很“弱”的源(包括SV源、甚至更弱的切合實(shí)際的“弱”源和“Block”源)對(duì)于模擬概率多項(xiàng)式時(shí)間的算法已經(jīng)足夠; 也就是說(shuō), 對(duì)于那些在本質(zhì)上不需要隨機(jī)源, 不過(guò)用隨機(jī)源時(shí)將潛在地提高效率的問(wèn)題來(lái)說(shuō), 用很“弱”的源已經(jīng)足夠。另外, 即使在以隨機(jī)源為基本考慮對(duì)象的密碼學(xué)(例如密鑰生成算法)中, 許多不可抽取的源(包括SV源等)足以適用于認(rèn)證應(yīng)用(例如適當(dāng)?shù)睦щy性假設(shè)下的消息認(rèn)證碼[16,38]及簽名方案[1,20])。直觀地講, 由于認(rèn)證應(yīng)用僅僅要求: 完全猜測(cè)(即偽造)某些長(zhǎng)布爾串對(duì)于攻擊者來(lái)說(shuō)是困難的, 因此知道源的最小熵就足以實(shí)現(xiàn)成功認(rèn)證。

4 基于非完美隨機(jī)源的隱私體制的安全性研究

該部分闡述抽取器、加密體制、承諾、秘密分享、零知識(shí)證明、差分隱私等涉及“隱私”的密碼體制(簡(jiǎn)稱為“隱私體制”)在非完美隨機(jī)源下的安全性結(jié)果。

4.1 基于非完美隨機(jī)源的傳統(tǒng)隱私體制

當(dāng)處理傳統(tǒng)隱私體制(例如抽取器、加密、承諾、秘密分享、零知識(shí)證明等)時(shí), 關(guān)于認(rèn)證的分析不再適用。首先, McInnes和Pinkas[37]得到了結(jié)論: 不能基于SV源來(lái)建立非條件安全的對(duì)稱加密方案, 即使限制為只加密1位。該結(jié)果接著被Dodis等人進(jìn)一步強(qiáng)化, 他們得到: SV源甚至不能用來(lái)構(gòu)造計(jì)算意義上安全的加密方案(即使是加密1位), 以及任意其它隱私體制(例如承諾、零知識(shí)、秘密分享等)[20]。Austrin等人[1]得到了更強(qiáng)的結(jié)果: 即使SV源可以高效取樣(efficient sampling), 這些負(fù)面結(jié)果仍然成立。另外, Bosley和Dodis[5]得到了甚至更負(fù)面的結(jié)果: 若隨機(jī)源足以用來(lái)生成一個(gè)能加密位的密鑰, 則能確定性地從該隨機(jī)源中抽取大約位幾乎均勻隨機(jī)位。這就意味著傳統(tǒng)隱私需要可抽取的隨機(jī)源。從積極方面講, 文獻(xiàn)[5]和[23]得到: 可抽取的源對(duì)于加密“很少的”幾位不是嚴(yán)格必需的。不過(guò), 對(duì)于自然的不可抽取的源(例如SV源)來(lái)說(shuō), 文獻(xiàn)[1,20,41]已得出結(jié)論: 即使僅加密1位也是不可能的。

4.2 基于非完美隨機(jī)源的差分隱私體制

盡管上述一系列負(fù)面結(jié)果似乎指明了方向: 隱私本質(zhì)上需要可抽取的隨機(jī)源, 但是最近Dodis等人[17]卻發(fā)現(xiàn)SV源足以實(shí)現(xiàn)隱私中的一個(gè)較新的概念(即差分隱私)。差分隱私的研究對(duì)象是統(tǒng)計(jì)數(shù)據(jù)庫(kù)。具有隱私保護(hù)作用的統(tǒng)計(jì)數(shù)據(jù)庫(kù)能保證在不泄漏用戶的私密數(shù)據(jù)的情況下, 讓他人獲得較寬松的統(tǒng)計(jì)事實(shí)。差分隱私可保證刪除或添加數(shù)據(jù)庫(kù)的一條記錄不會(huì)(大幅)影響體制的輸出。通俗地講, 體制(;) 把隨機(jī)值(即“噪音”)添到真實(shí)回答() 中去, 這里為用戶構(gòu)成的敏感數(shù)據(jù)庫(kù),() 為關(guān)于的用戶的一些有用的聚合信息。該噪音以某種方式添進(jìn)去, 滿足以下兩條似乎相沖突的性質(zhì):

加法噪音機(jī)制[18,27,28]具有形式()()(),其中為一個(gè)適當(dāng)?shù)摹霸胍簟狈植? 被加到真實(shí)回答中以保證有差分隱私性。例如, 對(duì)于完美隨機(jī)源來(lái)說(shuō), 當(dāng)考慮統(tǒng)計(jì)查詢時(shí), 適當(dāng)?shù)姆植紴槔绽狗植糩18]。然而, 對(duì)于SV源來(lái)說(shuō), 我們不能找到參數(shù)合適的拉普拉斯分布來(lái)得到差分隱私機(jī)制。事實(shí)上, 若存在基于非完美隨機(jī)源的具有差分隱私性和效用性的機(jī)制, 則存在基于該源的隨機(jī)抽取器, 故由SV源的不可抽取性可得:對(duì)于SV源來(lái)說(shuō), 不存在具有差分隱私性和效用性的加法噪音機(jī)制[17]。從另一個(gè)角度講, 不妨設(shè)T(=12)為滿足(D, f;)=的構(gòu)成的集合, 加法噪音機(jī)制必須滿足, 在此基礎(chǔ)上, SV敵手總能成功地?cái)U(kuò)大比率[24]或[17]。

盡管不存在基SV源的形如()=()+() 的加法噪音差分隱私機(jī)制, 這里為漢明重量函數(shù), 但Dodis等人[17]于2012年構(gòu)造出了一個(gè)結(jié)構(gòu)更好的機(jī)制, 該機(jī)制關(guān)于這種源具有差分隱私性。更具體地, 他們采用“一致采樣”(即“consistent sampling”)來(lái)建立SV-魯棒的機(jī)制[17], 并從SV源的位到位的性質(zhì)出發(fā)引入了另一條件。這兩個(gè)條件的組合稱為SV-一致采樣。他們還利用截?cái)嗪退阈g(shù)編碼等技術(shù)構(gòu)造了明確的具有差分隱私性和效用性的拉普拉斯機(jī)制。這樣的機(jī)制對(duì)于所有的SV分布來(lái)說(shuō)都適用, 前提是效用的上界被放松為關(guān)于1的多項(xiàng)式, 該多項(xiàng)式的度和系數(shù)依賴于而不依賴于數(shù)據(jù)庫(kù)的規(guī)模。另外, 值可以為任意小的常數(shù)(例如遠(yuǎn)遠(yuǎn)小于)。這與傳統(tǒng)隱私中的基于SV源的不可能性結(jié)果[37,20]不同, 那里=?()(意味著連固定常數(shù)安全都不可能實(shí)現(xiàn), 更不用說(shuō)安全參數(shù)為“可忽略的”的值時(shí)的情形了)。這些結(jié)果表明傳統(tǒng)隱私與差分隱私有一定的差距。Dodis等人[17]留下公開(kāi)問(wèn)題: 差分隱私能否建立在比SV源更切合實(shí)際的源上？由于BCL源和Block源比SV源更切合實(shí)際, 因此, 能否利用BCL源、Block源等來(lái)構(gòu)造差分隱私體制是一個(gè)很有意義的課題。

4.3 最新進(jìn)展

以該問(wèn)題為部分動(dòng)機(jī), Dodis和Yao[24]在CRYPTO 2015 中引入了一個(gè)直觀的、模塊化的框架來(lái)研究關(guān)于傳統(tǒng)隱私和差分隱私的不可能性結(jié)果, 這些結(jié)果是基于一般的非完美隨機(jī)源的。該結(jié)果統(tǒng)一并強(qiáng)化了觀點(diǎn): 多數(shù)情況下, 對(duì)于非完美隨機(jī)源來(lái)說(shuō), 隱私是不可能的, 除非該源是(幾乎)確定性可抽取的[24]。

整體思路

Dodis和Yao[24]引入了源的可表達(dá)性和可分離性的概念來(lái)衡量秘密的“非完美性”。從高層面上說(shuō), 文獻(xiàn)[24]借鑒文獻(xiàn)[20](那里只集中于研究SV源)中的思想, 不過(guò)以一種更模塊化和量上最優(yōu)化的方式來(lái)研究, 從而使得其證明在某種程度上更富有啟發(fā)性[24]。從本質(zhì)上說(shuō), 這些結(jié)果利用3步得到了基于非完美隨機(jī)源的一個(gè)給定的隱私體制的不可能性結(jié)果:

在這一抽象下, 容易得出: 多數(shù)隱私體制(例如抽取器、加密、秘密分享、承諾)的某種程度的安全性與的可表達(dá)性相矛盾。例如, 當(dāng)是加密方案時(shí),() 和()理解為密鑰下的兩個(gè)不同明文的加密函數(shù)。對(duì)于抽取、秘密分享及承諾有相似的討論。

更有趣的是, 文獻(xiàn)[24]得出結(jié)論: 若源是某種程度上可表達(dá)的, 則不可實(shí)現(xiàn)基于該源的某種程度的差分隱私。該證明與隱私體制的不可能性結(jié)果的證明有相似處, 但前者包含的思想更豐富。這是因?yàn)椴罘蛛[私性僅僅限制了“相接近的”數(shù)據(jù)庫(kù)的安全性, 而效用性則僅對(duì)于相對(duì)“遠(yuǎn)”的數(shù)據(jù)庫(kù)是有意義的。特別地, 正因如此, 源上的可表達(dá)性的要求對(duì)于排除差分隱私來(lái)說(shuō), 與傳統(tǒng)隱私相比要稍微強(qiáng)一些。除了這點(diǎn)量上的不同, 在文獻(xiàn)[24]的討論中傳統(tǒng)隱私和差分隱私?jīng)]有質(zhì)上的不同。

總之, 看似簡(jiǎn)單的“把隱私歸約為可表達(dá)性”的討論正是文獻(xiàn)[24]的框架的一個(gè)特征, 僅僅在這一步涉及應(yīng)用的具體細(xì)節(jié)。接著將集中于研究源。

文獻(xiàn)[24]證明了由可分離性一般可推導(dǎo)出可表達(dá)性, 前后兩者的參數(shù)幾乎相同。這恰恰是文獻(xiàn)[24]不同于[20]且在量上改進(jìn)文獻(xiàn)[20]的地方: 文獻(xiàn)[20]用了位到位的混合討論來(lái)闡明SV源的可表達(dá)性, 而文獻(xiàn)[24]則采用了更聰明的“universal hashing trick”來(lái)證明, 從而使得其結(jié)果與函數(shù)和的值域無(wú)關(guān)(此值域?qū)?yīng)于密文、承諾及秘密分享等的規(guī)模)。(a) 被抽取的位可保證是幾乎無(wú)偏的, (b) 盡管抽取器可能輸出, 但它至少在均勻分布上將以足夠大的概率輸出0或1。

與步驟1相結(jié)合, 文獻(xiàn)[24]得到以下兩個(gè)結(jié)果。首先, 把基于源的幾種隱私體制的不可能性結(jié)果歸約為一個(gè)更簡(jiǎn)單的的可分離性。第二, 把基于的的可行性結(jié)果歸約為基于的確定性弱位抽取的存在性?；仡橞osley和Dodis的結(jié)果: 由幾種傳統(tǒng)的隱私原語(yǔ)(僅包括多位的加密和承諾, 但不包括秘密分享)的安全性可推出多位確定性抽取器的存在性[5]。從而文獻(xiàn)[24]不可比擬地對(duì)上述結(jié)果進(jìn)行了補(bǔ)充。從積極方面來(lái)說(shuō), Dodis和Yao[24]的結(jié)果可應(yīng)用于更廣泛的隱私原語(yǔ)(例如秘密分享、一位加密和承諾)。從消極方面來(lái)說(shuō), Dodis和Yao[24]僅討論一種相對(duì)弱的一位抽取器, 這里的抽取器可能輸出, 而B(niǎo)osley和Dodis[5]則得到了傳統(tǒng)的可能多位的抽取器。

步驟3 幾種源R的可分離性。與文獻(xiàn)[1,20,37]中的結(jié)果不同, 上述所有結(jié)果對(duì)于任意非完美隨機(jī)源來(lái)說(shuō)都是正確的。為了得到基于自然源的隱私的不可能性結(jié)果, 必須確定具體的源的比較好的可分離性界。由文獻(xiàn)[20]可得SV 源和一般的弱源的可分離性界, 文獻(xiàn)[24]證明了Block源[13]和BCL源[19]的新的可分離性界。特別地, Block源的可分離性界是不容易得到的, 是文獻(xiàn)[24]的亮點(diǎn)之一。

這些Block源和BCL源的新的可分離性結(jié)果除了其自身的價(jià)值之外, 對(duì)差分隱私的研究也是很有意義的(見(jiàn)下面)。事實(shí)上, 這兩者都可被看做是對(duì)結(jié)構(gòu)化很強(qiáng)的(且不切實(shí)際的！)SV源的一種切合實(shí)際的放松, 不過(guò)不如弱源更一般/非結(jié)構(gòu)化。既然已經(jīng)得出對(duì)于SV源來(lái)說(shuō), 差分隱私是可行的, 那么一個(gè)自然的問(wèn)題是研究當(dāng)源慢慢地變得更切合實(shí)際/非結(jié)構(gòu)化, 且在變成一般的弱源之前, 能以多快的速度回歸為不可能性結(jié)果。

把新的和舊的不可能性結(jié)果綜合起來(lái)

把步驟1-3應(yīng)用于具體的源(即弱源、Block源、SV源及BCL源), 我們立刻得到關(guān)于傳統(tǒng)隱私的各種不可能性結(jié)果。雖然這些結(jié)果主要為關(guān)于差分隱私的(全新的)不可能性結(jié)果的基礎(chǔ), 它們也對(duì)文獻(xiàn)[20]的結(jié)果在量上進(jìn)行了改進(jìn)(源于從更強(qiáng)的可表達(dá)性到可分離性的歸約)。例如, 它們甚至排除了常數(shù)(與可忽略的值構(gòu)成對(duì)比)安全的加密/承諾/秘密分享, 且與密文/承諾/分享的規(guī)模無(wú)關(guān)。相關(guān)地, 我們自然地得到了關(guān)于Block/BCL源的比SV源更強(qiáng)的不可能性結(jié)果。

更有價(jià)值的是, 文獻(xiàn)[24]得到了第一個(gè)基于非完美隨機(jī)源的關(guān)于差分隱私的不可能性結(jié)果。受文獻(xiàn)[17]的正面結(jié)果的啟發(fā), 文獻(xiàn)[24]的關(guān)于非完美隨機(jī)源的可分離性結(jié)果(僅僅)對(duì)基于SV源的差分隱私體制的不可能性結(jié)果無(wú)效。正如文獻(xiàn)[24]所解釋的, 導(dǎo)致這一失敗的原因不是文獻(xiàn)[24]的框架太弱而不能應(yīng)用于SV源或差分隱私, 而是由于差分隱私中隱私和效用之間的“部分與全體之間的差距”。

然而, 一旦我們考慮一般的弱源, 或結(jié)構(gòu)化更強(qiáng)的Block/BCL源, 將很快地得到相應(yīng)的不可能性結(jié)果！例如, 當(dāng)研究效用為的-差分隱私時(shí), 最小熵為(其中)的位弱源將被排除, 更一般地, 不管塊數(shù)為多少, 每塊長(zhǎng)度為, 且每塊的最小熵為(其中)的-位Block源也將被排除。

不過(guò)Dodis和Yao[24]只考慮了加密體制中的1位對(duì)稱加密體制, 且密鑰取自非完美隨機(jī)源的情形。公鑰加密體制中,為了實(shí)現(xiàn)其標(biāo)準(zhǔn)的IND-CPA安全性, 不僅要求公鑰和消息是隨機(jī)的, 對(duì)于每個(gè)和每次加密來(lái)說(shuō), 還需引入新鮮獨(dú)立的隨機(jī)字串。Bellare等人[4]定義并設(shè)計(jì)了新型的公鑰加密體制(即hedged公鑰加密),該體制只需消息和其它隨機(jī)變量構(gòu)成的聯(lián)合分布有足夠的信息熵, 就能保證其體制的安全性?？梢?jiàn), 若把密鑰之外的其他隨機(jī)因素考慮進(jìn)去, 有望得到隱私體制的正面的安全性結(jié)果。

5 計(jì)算理論意義下基于弱隨機(jī)密鑰的密碼學(xué)原語(yǔ)的安全性研究

密碼學(xué)原語(yǔ)的安全性[25]可形式化地定義如下:

令表示由運(yùn)行時(shí)間、電路規(guī)模、預(yù)言機(jī)的詢問(wèn)數(shù)等構(gòu)成的元組。假設(shè)敵手A知道。對(duì)于任意, 令() 表示當(dāng)密鑰為時(shí)敵手A的攻擊優(yōu)勢(shì)。密碼學(xué)原語(yǔ)在理想模型(或現(xiàn)實(shí)模型)下是()-安全的, 若對(duì)于知道的任意敵手A來(lái)說(shuō),f(U)(或())的期望的上界為, 這里U表示{0,1}上的均勻分布(表示某非均勻分布)。()的期望稱為弱期望。例如, 對(duì)于CPA-安全的對(duì)稱加密方案來(lái)說(shuō), 敵手的“資源”=(), 這里為敵手的運(yùn)行時(shí)間,為敵手A的總的加密詢問(wèn)次數(shù)。特別地, 允許敵手A(適應(yīng)性地)向挑戰(zhàn)者對(duì)任意-1條消息1,…,s1進(jìn)行密鑰為的加密詢問(wèn), (在任意時(shí)刻)進(jìn)行一次“挑戰(zhàn)詢問(wèn)”(0*,1*)。對(duì)于挑戰(zhàn)詢問(wèn)來(lái)說(shuō), 挑戰(zhàn)者均勻隨機(jī)地選取, 然后返回s*的加密。最后, 敵手輸出一位“”, 若, 則敵手贏得了該游戲。敵手在密鑰上的攻擊優(yōu)勢(shì)() 為Pr[]-1/2。

根據(jù)安全模型的選取特點(diǎn), 我們把常用的密碼學(xué)原語(yǔ)分為不可預(yù)測(cè)性應(yīng)用(例如單向函數(shù)、消息認(rèn)證碼及簽名方案)和不可區(qū)分性應(yīng)用(例如CPA-安全的對(duì)稱加密方案、弱偽隨機(jī)函數(shù)、抽取器以及非延展抽取器)。“不可預(yù)測(cè)性”描述在安全游戲中敵手難以預(yù)測(cè)新的合理的“對(duì)”這一性質(zhì),“不可區(qū)分性”則表示敵手難于區(qū)分“挑戰(zhàn)對(duì)”。

Dodis和Yu[25]得到了關(guān)于()的不等式, 該不等式把()的弱期望的上界表示為兩部分的積: 第一部分只依賴于熵缺陷(即弱隨機(jī)密鑰的長(zhǎng)度=length() 和熵之間的差), 第二部分依賴于(U) 或(U)2的期望,即敵手在服從均勻分布的理想密鑰下的平均攻擊優(yōu)勢(shì)。得出結(jié)論: 當(dāng)敵手的攻擊能力有限時(shí), 在密鑰的熵缺損足夠小的前提下, 若一個(gè)密碼體制(包括不可預(yù)測(cè)性體制和“square-friendly”的不可區(qū)分性體制)在均勻隨機(jī)密鑰源下是計(jì)算理論意義上安全的, 則當(dāng)其中的密鑰用弱密鑰來(lái)代替時(shí), 其安全性不會(huì)受到很大影響。更具體地, 有下述兩個(gè)結(jié)果:

結(jié)果1: 若不可預(yù)測(cè)性應(yīng)用在理想模型下是()-安全的, 則應(yīng)用在密鑰的最小熵滿足的現(xiàn)實(shí)模型下是-安全的。

結(jié)果2: 若“square-friendly”不可區(qū)分性應(yīng)用在理想模型下是-安全和-可模擬的, 則應(yīng)用在密鑰的碰撞熵滿足的現(xiàn)實(shí)模型下是-安全的。

與之前針對(duì)具體的密碼學(xué)原語(yǔ)進(jìn)行研究(例如, 文獻(xiàn) [16,38] 巧妙地分析了基于弱源的(信息論上)的一次消息認(rèn)證碼的安全性)不同, 文獻(xiàn)[25]對(duì)多種密碼學(xué)原語(yǔ)的安全性進(jìn)行抽象和概括, 從統(tǒng)一的角度去研究。不過(guò)結(jié)果1只研究了最小熵時(shí)的情形, 結(jié)果2只研究了碰撞熵時(shí)的情形。而Rényi熵作為最一般的熵概念(它涵蓋了最小熵、碰撞熵、Shannon熵和其它一些熵[39]), 為我們提供了一個(gè)新的更一般的對(duì)密鑰隨機(jī)性的測(cè)量方法。Yao和Li[45]以H?lder不等式為基本工具, 通過(guò)挖掘Rényi熵與碰撞熵之間的聯(lián)系和概率函數(shù)()的不同階矩之間的關(guān)系, 把上述結(jié)論擴(kuò)充到了Rényi熵時(shí)的情形, 得出類似的結(jié)論。然而, 文獻(xiàn)[25]和[45]僅研究了當(dāng)密鑰的熵給定時(shí)的情形, 且其結(jié)果不能涵蓋一次性密鑰加密算法、偽隨機(jī)數(shù)生成器(PRG)等非“square-friendly”的不可區(qū)分性體制。若密鑰取自其它非完美隨機(jī)源(例如Block源、SV源、偏差控制受限源)時(shí), 文獻(xiàn)[25,45]卻沒(méi)法充分利用源的信息來(lái)分析密碼體制的安全性, 更不涉及明文等也取自非完美隨機(jī)源的情形。

Backes等人[9]研究了基于最大熵和最小熵被限定的秘密源(例如SV源)的密碼學(xué)原語(yǔ)的安全缺損的量化方法, 得出結(jié)論: 若秘密服從均勻隨機(jī)分布時(shí), 兩個(gè)體制0和1是不可區(qū)分的, 則當(dāng)秘密用滿足該限定條件的弱隨機(jī)秘密來(lái)代替時(shí), 這兩個(gè)體制在某種程度上是差分不可區(qū)分的。這里的秘密包括密鑰和加密過(guò)程中引入的隨機(jī)值等。該結(jié)論為我們研究基于非完美隨機(jī)源的密碼學(xué)原語(yǔ)的安全性提供了潛在的工具——“差分不可區(qū)分”模型, 但離解決“若秘密取自非完美隨機(jī)源時(shí),體制0和1是否仍為不可區(qū)分的？”這一問(wèn)題還有很大差距。

6 結(jié)束語(yǔ)

基于非完美隨的密碼學(xué)原語(yǔ)的安全性研究是一個(gè)較新的研究課題。對(duì)該課題的研究方興未艾, 盡管已取得了一些成果, 但仍有許多值得探索的問(wèn)題, 下面列舉幾個(gè), 希望能達(dá)到拋磚引玉的目的。

(1) 研究更復(fù)雜場(chǎng)景下的隱私問(wèn)題的不可能性結(jié)果;

(2) 挖掘并形式化新型的切合實(shí)際的非完美隨機(jī)源, 并研究關(guān)于隱私問(wèn)題的不可能性結(jié)果;

(3) 構(gòu)造基于新型的非完美隨機(jī)源的差分隱私機(jī)制;

(4) 在弱隨機(jī)密鑰服從SV分布、Block分布或偏差控制受限分布, 且敵手的攻擊能力有限的前提下, 系統(tǒng)深入地研究基于這種弱隨機(jī)密鑰的密碼學(xué)原語(yǔ)與基于均勻隨機(jī)密鑰的密碼學(xué)原語(yǔ)之間的內(nèi)在聯(lián)系,探索影響密碼學(xué)原語(yǔ)的安全性的本質(zhì)因素, 最終得出基于弱隨機(jī)密鑰的密碼學(xué)原語(yǔ)的安全性的一般性結(jié)論。

致 謝 本課題得到國(guó)家863計(jì)劃(No.2015AA016004), 國(guó)家自然科學(xué)基金(Nos.61170189,61370126,61202239), 北航軟件開(kāi)發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室探索性自選課題以及校級(jí)基本科研業(yè)務(wù)費(fèi)項(xiàng)目(No.30486301)資助。

[1] Austrin P., Chung K.M., Mahmoody M., et al. On the Impossibility of Cryptography with Tamperable Randomness., vol.8616 of LNCS, pp. 462-479

[2] Andreev A.E., Clementi A.E.F., Rolim J.D.P., et al. Weak random sources, hitting sets, and BPP simulations., 1999, 28(6): 2103-2116

[3] Alwen J., Dodis Y., and Wichs D. Survey: Leakage Resilience and the Bounded Retrieval Model., pp. 1-18

[4] Bellare M., Brakerski Z., Naor M., et al. Hedged public-key encryption: How to protect against bad randomness., pp. 232–249

[5] Bosley C. and Dodis Y. Does privacy require true randomness?, vol. 4392 of LNCS, pp. 1-20

[6] Boyen X., Dodis Y., Katz J., et al. Secure remote authentication using biometric data., vol. 3494 of LNCS, pp. 147-163

[7] Brakerski Z. and Goldwasser S. Circular and Leakage Resilient Public-Key Encryption under Subgroup Indistinguishability -(or: Quadratic Residuosity Strikes Back)., pp.1-20

[8] Barak B. and Halevi S. A model and architecture for pseudo- random generation with applications to /dev/random., pp. 203-212

[9] Backes M., Kate A., Meiser S., and Ruffing T. Secrecy Without Perfect Randomness: Cryptography with (Bounded) Weak Sources., pp. 675-695

[10] Blum M. Independent unbiased coin-flips from a correclated biased source-a finite state Markov chain., 1986, 6(2): pp. 97-108

[11] Barak B., Shaltiel R., and Tromer E. True random number generators secure in a changing environment. In:: pp. 166-180

[12] Chor B., Friedman J., Goldreich O., et al. The Bit Extraction Problem or t-resilient Functions. In, 1985: pp. 396-407

[13] Chor B., Goldreich O. Unbiased bits from sources of weak randomness and probabilistic communication complexity., 1988, 17(2): 230-261

[14] Clément Louis Canonne, Venkatesan Guruswami, Raghu Meka, and Madhu Sudan. Communication with Imperfectly Shared Randomness.: 257-262

[15] Chen R., Mu Y., Yang G., et al. Strongly Leakage-Resilient Authenticated Key Exchange., pp. 19-36

[16] Dodis Y., Katz J., Reyzin L., and Smith A. Robust fuzzy extractors and authenticated key agreement from close secrets., vol. 4117 of LNCS, pp. 232-250

[17] Dodis Y., López-Alt A., Mironov I., and Vadhan S.P. Differential Privacy with Imperfect Randomness., pp. 497-516

[18] Dwork C., McSherry F., Nissim K., and Smith A. Calibrating noise to sensitivity in private data analysis., vol. 3876 of LNCS, pp. 265-284

[19] Dodis Y. New Imperfect Random Source with Applications to Coin-Flipping., pp. 297-309

[20] Dodis Y., Ong S.J., Prabhakaran M., and Sahai A. On the (im)possibility of cryptography with imperfect randomness., pp. 196-205

[21] Dodis Y., Ostrovsky R., Reyzin L., Smith A. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data., 2008, 38(1): 97-139

[22] Deng H., Qin B., Du R.Y., Zhang H.G., et al. Finding Key Leakage in Hierarchical Distribution of Encrypted Data., pp. 780-785

[23] Dodis Y., Spencer J. On the (non) Universality of the One-Time Pad., pp. 376-385

[24] Dodis Y. and Yao Y.Q. Privacy and Imperfect Randomness., vol. 9216 of LNCS, pp. 463-482

[25] Dodis Y. and Yu Y. Overcoming Weak Expectations., pp. 1-22

[26] Gennaro R., Krawczyk H., and Rabin T. Secure hashed diffie- hellman over non-ddh groups., vol. 3027 of LNCS, pp. 361-381

[27] Ghosh A., Roughgarden T., and Sundararajan M. Universally utility maximizing privacy mechanisms., pp. 351-360

[28] Hardt M. and Talwar K. On the geometry of differential privacy., pp. 705-714

[29] Hu C.Y., Yu Z.X., Yang R.P., Xu Q.L., et al. Weak leakage resilient extractable hash proof system and construction for weak leakage resilient CCA-secure public-key encryption., 7(3/4), pp. 216-229

[30] Ishai Y., Weiss M., and Yang G. Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage- Resilient Circuits., pp. 3-32

[31] Krawczyk H. Cryptographic Extraction and Key Derivation: The HKDF Scheme., vol. 6223 of LNCS, pp. 631-648

[32] Kamp J. and Zuckerman D. Deterministic extractors for bit-fixing sources and exposure resilient cryptography. In, pp. 92-101

[33] Liu S.L.Biometric-based key generation., no 12, 2009. (劉勝利. 基于生物特征的密鑰提取., 2009年第12期.)

[34] Lichtenstein D., Linial N., Saks M.E. Some extremal problems arising from discrete control processes., 1989, 9(3), 269-287

[35] Liu S.L., Weng J., Zhao Y.L. Efficient Public Key Cryptosystem Resilient to Key Leakage Chosen Ciphertext Attacks., pp. 84-100

[36] Li Z.Q., Zhang B., Yao Y., Lin D.D. Cube Cryptanalysis of LBlock with Noisy Leakage., pp. 141-155

[37] James L. McInnes and Benny Pinkas. On the impossibility of private key cryptography with weakly random keys., vol. 537 of LNCS, pp. 421-435

[38] Maurer U.M., Wolf S. Privacy amplification secure against active adversaries., vol. 1294 of LNCS, pp. 307-321

[39] Rényi, A. On measures of information and entropy., pp. 547-561, 1960

[40] Standaert F.X., Pereira O., Yu Y., et al. Leakage Resilient Cryptography in Practice., pp. 99-134 , 2010

[41] Santha M. and Vazirani U.V. Generating quasi-random sequences from semirandom sources., 1986, 33(1): 75-87

[42] von Neumann J. Various techniques used in connection with random digits., 1951, 12: 36-38

[43] Vazirani U.V. and Vazirani V.V. Random polynomial time is equal to slightly random polynomial time., pp. 417-428

[44] 姚燕青. 基于非完美隨機(jī)源的密碼學(xué)原語(yǔ)的安全性研究 [博士學(xué)位論文]. 學(xué)位授予單位地點(diǎn): 北京航空航天大學(xué), 2015年

[45] Yao Y.Q. and Li Z.J. Overcoming Weak Expectations via the Rényi Entropy and the Expanded Computational Entropy.), vol. 8317 of LNCS, pp. 162-178

[46] Zuckerman D. Simulating BPP using a general weak random source., 1996, 16(4/5): 367-391

[47] Zhang H., Zhou Y., and Feng D.G. An Efficient Leakage Characterization Method for Profiled Power Analysis Attacks., pp. 61-73

姚燕青 于2015年在北京航空航天大學(xué)計(jì)算機(jī)學(xué)院獲得博士學(xué)位?，F(xiàn)任北京航空航天大學(xué)計(jì)算機(jī)學(xué)院講師。主要研究領(lǐng)域?yàn)榛诜峭昝离S機(jī)源的密碼學(xué)、彈性泄漏非延展編碼等。Email: yaoyanqing1984 @buaa.edu.cn李舟軍 于1999年在國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院獲得博士學(xué)位?，F(xiàn)為北京航空航天大學(xué)計(jì)算機(jī)學(xué)院教授, 博士生導(dǎo)師, 信息安全系主任。主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)與信息安全技術(shù)、數(shù)據(jù)挖掘與人工智能。Email: lizj@buaa.edu.cn.

Survey: Security of Cryptographic Primitives with Imperfect Randomness

YAO Yanqing, LI Zhoujun

School of Computer Science and Engineering, Beihang University, Beijing 100191, China

Cryptography is a core area in information security. Traditional cryptographic primitives take for granted the availability of perfect random sources. However, in many situations it seems unrealistic to expect a source to be perfectly random, and one must deal with various imperfect sources of randomness. Some well known examples are physical sources, biometric data, secrets with partial leakage, etc. Hence, can cryptographic primitives with imperfect randomness be secure? It has become a frontier and hot research topic in Cryptography. This paper reviews the background, significance, and the development history of this topic. It also reviews the latest advances of this topic. Namely, some general impossibility results of traditional privacy (e.g., bit extractor, encryption, commitment, secret sharing scheme) and differential privacy under a general imperfect source proposed by Dodis and Yao in CRYPTO 2015. Finally, the paper analyzes the problems worth exploring in this area.

imperfect random sources; cryptographic primitives; security; traditional privacy; differential privacy

TP309.7

1:姚燕青, 博士, 講師, Email: yaoyanqing1984@buaa.edu.cn。通訊作者2:李舟軍, 博士, 教授, Email: lizj@buaa.edu.cn。

本課題得到國(guó)家863計(jì)劃(No.2015AA016004), 國(guó)家自然科學(xué)基金(Nos.61170189, 61370126, 61202239), 北航軟件開(kāi)發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室探索性自選課題以及校級(jí)基本科研業(yè)務(wù)費(fèi)項(xiàng)目(No.30486301)資助。

2015-11-29; 修改日期: 2016-4-19; 定稿日期: 2016-4-28

DOI號(hào) 10.19363/j.cnki.cn10-1380/tn.2016.02.003