姚燕青,李舟军



基于非完美随机源的密码学原语的安全性研究综述

姚燕青,李舟军

北京航空航天大学计算机学院 北京 中国 100191

密码学是信息安全的核心研究内容。传统的密码学原语理想地假设秘密服从均匀随机分布。然而, 在现实世界中往往并非如此。例如, 若秘密源为生物数据、物理源、部分泄漏的秘密等时, 相应的分布并不服从均匀分布。这样的一些分布构成的集合称为“非完美随机源”。因此, 基于非完美随机源的密码学原语是否仍具有安全性？这已成为当今密码学前沿研究领域的热点和难点课题之一。本文阐述了基于非完美随机源的密码学原语的研究背景、意义及发展历程, 重点介绍了该领域的最新进展, 即Dodis和Yao[CRYPTO 2015]发现的基于一般的非完美随机源的传统隐私(包括位抽取器、加密、承诺、秘密分享方案)和差分隐私的(不)可能性结果。最后, 指出了当前该领域值得探索的问题。

非完美随机源; 密码学原语; 安全性; 传统隐私; 差分隐私

1 引言

密码学是网络信息安全的理论基础和必要保证。密码系统的输出必须在敌手看来是一系列的随机值, 看起来与原始信息毫无关联。在设计密码系统时, 密钥必须为随机的, 否则破解密文将不再困难。密码学中著名的Kerckhoff准则为: “一个密码系统的安全性都应该基于密钥的安全性, 而不是基于算法的细节的安全性”。可见, 密钥的随机性在密码系统中起着极其关键的作用。在公钥加密体制中, 为了达到选择明文攻击下的不可区分性(简称为IND-CPA), 除了要求公钥和明文在敌手看来是随机的, 每次加密中还需引入新鲜独立的随机串。因此, 随机性在某种程度上决定了密码系统的安全性。

在传统的密码学研究中, 假设秘密服从均匀随机分布。密码应用大多适用算法来生成随机数。这些算法是确定的, 所以产生的序列并非统计随机的。但当算法好时, 产生的序列可以经受住随机性检测。这样的数称为伪随机数。然而在诸多现实应用中, 秘密连伪随机的要求都达不到。例如: 若秘密源为生物数据[6,21]、物理源[8,11]、部分泄漏的秘密[3,40]、Diffie- Hellman密钥交换中的群元素[26,31]时, 则它不是完美随机的。相应的分布不服从均匀分布。一些非均匀分布构成的集合称为“非完美随机源(Imperfect Random Source)”。例如, 多数已有的安全模型假设在加密过程中不会泄漏关于密钥和用于加密的随机值的信息, 而真实环境中敌手可能会通过各种密钥泄漏攻击(例如计算时间、功耗、故障检测、电磁辐射、散热等)来获得关于秘密状态的部分信息。又如, 有些机构利用生物特征来提取密钥, 由于生物特征(例如指纹、脸相、虹膜等)的唯一性和终身不变性, 用这种特征来提取密钥具有不被遗忘或丢失, 随身可用, 不易被伪造等优点, 不过这样的密钥亦不服从均匀分布。

密码学原语是密码系统的基本构件。密码学原语包括: 哈希函数、消息认证码、签名方案、抽取器、加密方案、承诺、秘密分享、差分隐私、密钥生成函数、伪随机数生成器等。当今密码学领域的一个研究热点和难点课题是: 原有的密码学原语在非完美随机源下是否仍然具有安全性？该领域的研究在秘密取自物理源、生物源、部分泄漏或篡改的秘密源的现实社会中具有广阔的应用前景。

1.1 国内外的相关研究团队

目前, 国际上已有一些著名研究团队研究基于非完美随机源的密码学, 如: 美国麻省理工学院的图灵奖获得者Shafi Goldwasser教授[7]的研究小组、哈佛大学的Vadhan和Sudan教授[14,17]的研究小组、美国纽约大学的Yevgeniy Dodis教授[5,17,20]的研究小组、美国University of Texasat Austin的David Zuckerman教授[32,46]的研究小组、以色列Weizmann Institute of Science的Moni Naor教授[4]的研究小组、澳大利亚伍伦贡大学的Yi Mu教授[15]的研究小组等。基于非完美随机源的密码体制(尤其是泄漏容忍的密码体制)也引起了国内一些机构的研究兴趣, 如中科院信息安全国家重点实验室[36,47]、清华大学[30]、上海交通大学[25,33]、武汉大学[22]、暨南大学[35]、山东大学[29]等。

到目前为止, 学者们已得到关于该课题的一些结果。概括来讲, 认证方案(例如消息认证码、数字签名方案)对于密钥的随机性程度的要求较为宽松[1,20,16,38], 但加密方案以及其他涉及“隐私”的方案却并非如此(例如, 文献[1,5,20,23,37,41])。本文将论述几种典型的非完美随机源, 然后分别阐述基于非完美随机源的认证方案、传统隐私体制、差分隐私体制的安全性研究的发展历程及发展动态, 其中将重点介绍 Dodis和Yao 在 CRYPTO 2015 中的最新结果, 接着介绍计算理论意义下基于弱随机密钥的密码学原语的安全性研究历程及存在的问题。最后, 指出该领域目前值得探索的问题。

2 非完美随机源模型

目前, 已出现了一些形式化的模型(例如弱源、Block源、Santha-Vazirani源、偏差控制受限源)来抽象非完美随机源[2,10,12,13,19,34,41,42,46]。粗略地说, 它们分为可抽取的和不可抽取的。位抽取问题可概括如下: 该问题有三个参数,, 和。用户选取函数, 敌手选取个输入位中的个位, 并对这个位的取值进行固定, 用户不知道敌手选了哪个位以及这个位的取值是多少。剩余的个输入位的取值为独立无偏的抛币游戏的输出。用户用函数作用于这位输入。用户的目标是使得函数的输出服从上的均匀分布, 而敌手的目标则是使得函数的输出分布是有偏的。位抽取问题归结为用户的取胜问题。文献[12]给出了使敌手失败的的上下界。概括地讲, 可抽取的源(例如文献[10,12,34,42])允许几乎均匀分布的确定性抽取。尽管使得抽取比率和效率最优化是很有趣的问题, 但从质的角度, 适用于完美随机源的应用中的源都可用可抽取的源来代替。不幸的是, 人们很快意识到现实中的许多源不是可抽取的(例如弱源、Block源、Santha-Vazirani源、偏差控制受限源)[13,19,41]。

Santha-Vazirani 源 Santha和Vazirani于1986年提出了Santha-Vazirani源[41](简记为SV源)。该源产生一系列的位12,, 满足这里为任意正整数。可高效取样的SV源[1]是逐位产生的, 对于产生的位r, 敌手在获悉已产生的1 个位12, …, r的信息的前提下, 以“在线”的方式高效地对服从均匀分布的r以独立概率进行篡改。不难看出, 在均匀随机的位二元串上进行上述篡改得到的随机变量服从的SV分布。事实上, 任何SV源既可看成物理源, 又可看成由敌手对均匀随机的位二元串进行上述篡改而得到的源[1]。不管有多少个SV位, 均不存在1位的确定性抽取器, 能够从SV源中抽取出偏差严格小于的1位[41]。

偏差控制受限源在现实世界中, 流源产生的每一位可能不是均匀随机的, 由于噪音、测量错误及其它一些缺陷, 微小的错误是不可避免的; 由于内部联系、测量条件限制或设置不当, 一些位非平凡地依赖于前面的位, 其极端情况是有的位由前面的位完全确定。2001年, Dodis[19]给出了对上述源的模型化表示, 称之为偏差控制受限源(简称为 BCL 源)。该源产生一系列的位12 ,…, x: 对12来说,x的值按以下两种方式之一依赖于12,x:

(A)x由12 ,…, x完全确定, 但这种情况发生的次数至多为某常数;

弱源和Block源 最小熵至少为的-位弱源(Weak Source) 定义为集合Block源作为弱源的推广, 允许有个块1,…,R, 每块在假设已知前面的块的前提下有新鲜的位熵。与SV源相比, Block源不含最大熵的信息, 从这个意义上来说, Block源的限制性更少, 也比SV源更切合实际。

3 基于非完美随机源的概率多项式时间的算法和认证研究

尽管不可抽取的源排除了对于所有应用来说从非完美源到完美源的“黑盒编译”, 但我们仍希望特定的不可抽取的源足以适用于模拟概率算法及密码学中的某些应用。一系列结果[2,13,41,43,46]表明: 很“弱”的源(包括SV源、甚至更弱的切合实际的“弱”源和“Block”源)对于模拟概率多项式时间的算法已经足够; 也就是说, 对于那些在本质上不需要随机源, 不过用随机源时将潜在地提高效率的问题来说, 用很“弱”的源已经足够。另外, 即使在以随机源为基本考虑对象的密码学(例如密钥生成算法)中, 许多不可抽取的源(包括SV源等)足以适用于认证应用(例如适当的困难性假设下的消息认证码[16,38]及签名方案[1,20])。直观地讲, 由于认证应用仅仅要求: 完全猜测(即伪造)某些长布尔串对于攻击者来说是困难的, 因此知道源的最小熵就足以实现成功认证。

4 基于非完美随机源的隐私体制的安全性研究

该部分阐述抽取器、加密体制、承诺、秘密分享、零知识证明、差分隐私等涉及“隐私”的密码体制(简称为“隐私体制”)在非完美随机源下的安全性结果。

4.1 基于非完美随机源的传统隐私体制

当处理传统隐私体制(例如抽取器、加密、承诺、秘密分享、零知识证明等)时, 关于认证的分析不再适用。首先, McInnes和Pinkas[37]得到了结论: 不能基于SV源来建立非条件安全的对称加密方案, 即使限制为只加密1位。该结果接着被Dodis等人进一步强化, 他们得到: SV源甚至不能用来构造计算意义上安全的加密方案(即使是加密1位), 以及任意其它隐私体制(例如承诺、零知识、秘密分享等)[20]。Austrin等人[1]得到了更强的结果: 即使SV源可以高效取样(efficient sampling), 这些负面结果仍然成立。另外, Bosley和Dodis[5]得到了甚至更负面的结果: 若随机源足以用来生成一个能加密位的密钥, 则能确定性地从该随机源中抽取大约位几乎均匀随机位。这就意味着传统隐私需要可抽取的随机源。从积极方面讲, 文献[5]和[23]得到: 可抽取的源对于加密“很少的”几位不是严格必需的。不过, 对于自然的不可抽取的源(例如SV源)来说, 文献[1,20,41]已得出结论: 即使仅加密1位也是不可能的。

4.2 基于非完美随机源的差分隐私体制

尽管上述一系列负面结果似乎指明了方向: 隐私本质上需要可抽取的随机源, 但是最近Dodis等人[17]却发现SV源足以实现隐私中的一个较新的概念(即差分隐私)。差分隐私的研究对象是统计数据库。具有隐私保护作用的统计数据库能保证在不泄漏用户的私密数据的情况下, 让他人获得较宽松的统计事实。差分隐私可保证删除或添加数据库的一条记录不会(大幅)影响体制的输出。通俗地讲, 体制(;) 把随机值(即“噪音”)添到真实回答() 中去, 这里为用户构成的敏感数据库,() 为关于的用户的一些有用的聚合信息。该噪音以某种方式添进去, 满足以下两条似乎相冲突的性质:

加法噪音机制[18,27,28]具有形式()()(),其中为一个适当的“噪音”分布, 被加到真实回答中以保证有差分隐私性。例如, 对于完美随机源来说, 当考虑统计查询时, 适当的分布为拉普拉斯分布[18]。然而, 对于SV源来说, 我们不能找到参数合适的拉普拉斯分布来得到差分隐私机制。事实上, 若存在基于非完美随机源的具有差分隐私性和效用性的机制, 则存在基于该源的随机抽取器, 故由SV源的不可抽取性可得:对于SV源来说, 不存在具有差分隐私性和效用性的加法噪音机制[17]。从另一个角度讲, 不妨设T(=12)为满足(D, f;)=的构成的集合, 加法噪音机制必须满足, 在此基础上, SV敌手总能成功地扩大比率[24]或[17]。

尽管不存在基SV源的形如()=()+() 的加法噪音差分隐私机制, 这里为汉明重量函数, 但Dodis等人[17]于2012年构造出了一个结构更好的机制, 该机制关于这种源具有差分隐私性。更具体地, 他们采用“一致采样”(即“consistent sampling”)来建立SV-鲁棒的机制[17], 并从SV源的位到位的性质出发引入了另一条件。这两个条件的组合称为SV-一致采样。他们还利用截断和算术编码等技术构造了明确的具有差分隐私性和效用性的拉普拉斯机制。这样的机制对于所有的SV分布来说都适用, 前提是效用的上界被放松为关于1的多项式, 该多项式的度和系数依赖于而不依赖于数据库的规模。另外, 值可以为任意小的常数(例如远远小于)。这与传统隐私中的基于SV源的不可能性结果[37,20]不同, 那里=Ω()(意味着连固定常数安全都不可能实现, 更不用说安全参数为“可忽略的”的值时的情形了)。这些结果表明传统隐私与差分隐私有一定的差距。Dodis等人[17]留下公开问题: 差分隐私能否建立在比SV源更切合实际的源上？由于BCL源和Block源比SV源更切合实际, 因此, 能否利用BCL源、Block源等来构造差分隐私体制是一个很有意义的课题。

4.3 最新进展

以该问题为部分动机, Dodis和Yao[24]在CRYPTO 2015 中引入了一个直观的、模块化的框架来研究关于传统隐私和差分隐私的不可能性结果, 这些结果是基于一般的非完美随机源的。该结果统一并强化了观点: 多数情况下, 对于非完美随机源来说, 隐私是不可能的, 除非该源是(几乎)确定性可抽取的[24]。

整体思路

Dodis和Yao[24]引入了源的可表达性和可分离性的概念来衡量秘密的“非完美性”。从高层面上说, 文献[24]借鉴文献[20](那里只集中于研究SV源)中的思想, 不过以一种更模块化和量上最优化的方式来研究, 从而使得其证明在某种程度上更富有启发性[24]。从本质上说, 这些结果利用3步得到了基于非完美随机源的一个给定的隐私体制的不可能性结果:

在这一抽象下, 容易得出: 多数隐私体制(例如抽取器、加密、秘密分享、承诺)的某种程度的安全性与的可表达性相矛盾。例如, 当是加密方案时,() 和()理解为密钥下的两个不同明文的加密函数。对于抽取、秘密分享及承诺有相似的讨论。

更有趣的是, 文献[24]得出结论: 若源是某种程度上可表达的, 则不可实现基于该源的某种程度的差分隐私。该证明与隐私体制的不可能性结果的证明有相似处, 但前者包含的思想更丰富。这是因为差分隐私性仅仅限制了“相接近的”数据库的安全性, 而效用性则仅对于相对“远”的数据库是有意义的。特别地, 正因如此, 源上的可表达性的要求对于排除差分隐私来说, 与传统隐私相比要稍微强一些。除了这点量上的不同, 在文献[24]的讨论中传统隐私和差分隐私没有质上的不同。

总之, 看似简单的“把隐私归约为可表达性”的讨论正是文献[24]的框架的一个特征, 仅仅在这一步涉及应用的具体细节。接着将集中于研究源。

文献[24]证明了由可分离性一般可推导出可表达性, 前后两者的参数几乎相同。这恰恰是文献[24]不同于[20]且在量上改进文献[20]的地方: 文献[20]用了位到位的混合讨论来阐明SV源的可表达性, 而文献[24]则采用了更聪明的“universal hashing trick”来证明, 从而使得其结果与函数和的值域无关(此值域对应于密文、承诺及秘密分享等的规模)。(a) 被抽取的位可保证是几乎无偏的, (b) 尽管抽取器可能输出, 但它至少在均匀分布上将以足够大的概率输出0或1。

与步骤1相结合, 文献[24]得到以下两个结果。首先, 把基于源的几种隐私体制的不可能性结果归约为一个更简单的的可分离性。第二, 把基于的的可行性结果归约为基于的确定性弱位抽取的存在性。回顾Bosley和Dodis的结果: 由几种传统的隐私原语(仅包括多位的加密和承诺, 但不包括秘密分享)的安全性可推出多位确定性抽取器的存在性[5]。从而文献[24]不可比拟地对上述结果进行了补充。从积极方面来说, Dodis和Yao[24]的结果可应用于更广泛的隐私原语(例如秘密分享、一位加密和承诺)。从消极方面来说, Dodis和Yao[24]仅讨论一种相对弱的一位抽取器, 这里的抽取器可能输出, 而Bosley和Dodis[5]则得到了传统的可能多位的抽取器。

步骤3 几种源R的可分离性。与文献[1,20,37]中的结果不同, 上述所有结果对于任意非完美随机源来说都是正确的。为了得到基于自然源的隐私的不可能性结果, 必须确定具体的源的比较好的可分离性界。由文献[20]可得SV 源和一般的弱源的可分离性界, 文献[24]证明了Block源[13]和BCL源[19]的新的可分离性界。特别地, Block源的可分离性界是不容易得到的, 是文献[24]的亮点之一。

这些Block源和BCL源的新的可分离性结果除了其自身的价值之外, 对差分隐私的研究也是很有意义的(见下面)。事实上, 这两者都可被看做是对结构化很强的(且不切实际的！)SV源的一种切合实际的放松, 不过不如弱源更一般/非结构化。既然已经得出对于SV源来说, 差分隐私是可行的, 那么一个自然的问题是研究当源慢慢地变得更切合实际/非结构化, 且在变成一般的弱源之前, 能以多快的速度回归为不可能性结果。

把新的和旧的不可能性结果综合起来

把步骤1-3应用于具体的源(即弱源、Block源、SV源及BCL源), 我们立刻得到关于传统隐私的各种不可能性结果。虽然这些结果主要为关于差分隐私的(全新的)不可能性结果的基础, 它们也对文献[20]的结果在量上进行了改进(源于从更强的可表达性到可分离性的归约)。例如, 它们甚至排除了常数(与可忽略的值构成对比)安全的加密/承诺/秘密分享, 且与密文/承诺/分享的规模无关。相关地, 我们自然地得到了关于Block/BCL源的比SV源更强的不可能性结果。

更有价值的是, 文献[24]得到了第一个基于非完美随机源的关于差分隐私的不可能性结果。受文献[17]的正面结果的启发, 文献[24]的关于非完美随机源的可分离性结果(仅仅)对基于SV源的差分隐私体制的不可能性结果无效。正如文献[24]所解释的, 导致这一失败的原因不是文献[24]的框架太弱而不能应用于SV源或差分隐私, 而是由于差分隐私中隐私和效用之间的“部分与全体之间的差距”。

然而, 一旦我们考虑一般的弱源, 或结构化更强的Block/BCL源, 将很快地得到相应的不可能性结果！例如, 当研究效用为的-差分隐私时, 最小熵为(其中)的位弱源将被排除, 更一般地, 不管块数为多少, 每块长度为, 且每块的最小熵为(其中)的-位Block源也将被排除。

不过Dodis和Yao[24]只考虑了加密体制中的1位对称加密体制, 且密钥取自非完美随机源的情形。公钥加密体制中,为了实现其标准的IND-CPA安全性, 不仅要求公钥和消息是随机的, 对于每个和每次加密来说, 还需引入新鲜独立的随机字串。Bellare等人[4]定义并设计了新型的公钥加密体制(即hedged公钥加密),该体制只需消息和其它随机变量构成的联合分布有足够的信息熵, 就能保证其体制的安全性。可见, 若把密钥之外的其他随机因素考虑进去, 有望得到隐私体制的正面的安全性结果。

5 计算理论意义下基于弱随机密钥的密码学原语的安全性研究

密码学原语的安全性[25]可形式化地定义如下:

令表示由运行时间、电路规模、预言机的询问数等构成的元组。假设敌手A知道。对于任意, 令() 表示当密钥为时敌手A的攻击优势。密码学原语在理想模型(或现实模型)下是()-安全的, 若对于知道的任意敌手A来说,f(U)(或())的期望的上界为, 这里U表示{0,1}上的均匀分布(表示某非均匀分布)。()的期望称为弱期望。例如, 对于CPA-安全的对称加密方案来说, 敌手的“资源”=(), 这里为敌手的运行时间,为敌手A的总的加密询问次数。特别地, 允许敌手A(适应性地)向挑战者对任意-1条消息1,…,s1进行密钥为的加密询问, (在任意时刻)进行一次“挑战询问”(0*,1*)。对于挑战询问来说, 挑战者均匀随机地选取, 然后返回s*的加密。最后, 敌手输出一位“”, 若, 则敌手赢得了该游戏。敌手在密钥上的攻击优势() 为Pr[]-1/2。

根据安全模型的选取特点, 我们把常用的密码学原语分为不可预测性应用(例如单向函数、消息认证码及签名方案)和不可区分性应用(例如CPA-安全的对称加密方案、弱伪随机函数、抽取器以及非延展抽取器)。“不可预测性”描述在安全游戏中敌手难以预测新的合理的“对”这一性质,“不可区分性”则表示敌手难于区分“挑战对”。

Dodis和Yu[25]得到了关于()的不等式, 该不等式把()的弱期望的上界表示为两部分的积: 第一部分只依赖于熵缺陷(即弱随机密钥的长度=length() 和熵之间的差), 第二部分依赖于(U) 或(U)2的期望,即敌手在服从均匀分布的理想密钥下的平均攻击优势。得出结论: 当敌手的攻击能力有限时, 在密钥的熵缺损足够小的前提下, 若一个密码体制(包括不可预测性体制和“square-friendly”的不可区分性体制)在均匀随机密钥源下是计算理论意义上安全的, 则当其中的密钥用弱密钥来代替时, 其安全性不会受到很大影响。更具体地, 有下述两个结果:

结果1: 若不可预测性应用在理想模型下是()-安全的, 则应用在密钥的最小熵满足的现实模型下是-安全的。

结果2: 若“square-friendly”不可区分性应用在理想模型下是-安全和-可模拟的, 则应用在密钥的碰撞熵满足的现实模型下是-安全的。

与之前针对具体的密码学原语进行研究(例如, 文献 [16,38] 巧妙地分析了基于弱源的(信息论上)的一次消息认证码的安全性)不同, 文献[25]对多种密码学原语的安全性进行抽象和概括, 从统一的角度去研究。不过结果1只研究了最小熵时的情形, 结果2只研究了碰撞熵时的情形。而Rényi熵作为最一般的熵概念(它涵盖了最小熵、碰撞熵、Shannon熵和其它一些熵[39]), 为我们提供了一个新的更一般的对密钥随机性的测量方法。Yao和Li[45]以Hölder不等式为基本工具, 通过挖掘Rényi熵与碰撞熵之间的联系和概率函数()的不同阶矩之间的关系, 把上述结论扩充到了Rényi熵时的情形, 得出类似的结论。然而, 文献[25]和[45]仅研究了当密钥的熵给定时的情形, 且其结果不能涵盖一次性密钥加密算法、伪随机数生成器(PRG)等非“square-friendly”的不可区分性体制。若密钥取自其它非完美随机源(例如Block源、SV源、偏差控制受限源)时, 文献[25,45]却没法充分利用源的信息来分析密码体制的安全性, 更不涉及明文等也取自非完美随机源的情形。

Backes等人[9]研究了基于最大熵和最小熵被限定的秘密源(例如SV源)的密码学原语的安全缺损的量化方法, 得出结论: 若秘密服从均匀随机分布时, 两个体制0和1是不可区分的, 则当秘密用满足该限定条件的弱随机秘密来代替时, 这两个体制在某种程度上是差分不可区分的。这里的秘密包括密钥和加密过程中引入的随机值等。该结论为我们研究基于非完美随机源的密码学原语的安全性提供了潜在的工具——“差分不可区分”模型, 但离解决“若秘密取自非完美随机源时,体制0和1是否仍为不可区分的？”这一问题还有很大差距。

6 结束语

基于非完美随的密码学原语的安全性研究是一个较新的研究课题。对该课题的研究方兴未艾, 尽管已取得了一些成果, 但仍有许多值得探索的问题, 下面列举几个, 希望能达到抛砖引玉的目的。

(1) 研究更复杂场景下的隐私问题的不可能性结果;

(2) 挖掘并形式化新型的切合实际的非完美随机源, 并研究关于隐私问题的不可能性结果;

(3) 构造基于新型的非完美随机源的差分隐私机制;

(4) 在弱随机密钥服从SV分布、Block分布或偏差控制受限分布, 且敌手的攻击能力有限的前提下, 系统深入地研究基于这种弱随机密钥的密码学原语与基于均匀随机密钥的密码学原语之间的内在联系,探索影响密码学原语的安全性的本质因素, 最终得出基于弱随机密钥的密码学原语的安全性的一般性结论。

致 谢 本课题得到国家863计划(No.2015AA016004), 国家自然科学基金(Nos.61170189,61370126,61202239), 北航软件开发环境国家重点实验室探索性自选课题以及校级基本科研业务费项目(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] 姚燕青. 基于非完美随机源的密码学原语的安全性研究 [博士学位论文]. 学位授予单位地点: 北京航空航天大学, 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年在北京航空航天大学计算机学院获得博士学位。现任北京航空航天大学计算机学院讲师。主要研究领域为基于非完美随机源的密码学、弹性泄漏非延展编码等。Email: yaoyanqing1984 @buaa.edu.cn李舟军 于1999年在国防科学技术大学计算机学院获得博士学位。现为北京航空航天大学计算机学院教授, 博士生导师, 信息安全系主任。主要研究领域为网络与信息安全技术、数据挖掘与人工智能。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。

本课题得到国家863计划(No.2015AA016004), 国家自然科学基金(Nos.61170189, 61370126, 61202239), 北航软件开发环境国家重点实验室探索性自选课题以及校级基本科研业务费项目(No.30486301)资助。

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

DOI号 10.19363/j.cnki.cn10-1380/tn.2016.02.003