Page 269 - 《软件学报》2021年第9期

康步荣 等:抗随机数后门攻击的密码算法 2893

2.4 有待深入研究的问题
关于对冲公钥加密算法,我们总结了如下几个需要进一步研究的问题.
1) 现有对冲公钥加密算法都依赖随机预言模型,而该模型是密码学中的一个理想化模型,现实世界中并
不存在.如何构造基于标准模型下的对冲公钥机密算法,将是值得继续研究的一个方向;
2) 目前,关于对冲公钥加密算法的安全性研究存在一个一般性问题,就是没有一个安全性质可以适用于
所有的对冲公钥加密算法.所以,研究对冲公钥加密算法的一般性安全性质是值得探索的方向;
3) 对冲公钥加密算法通常要求明文消息和相应随机数(或随机填充值)的联合分布是高熵的.若明文空
间较小,对冲公钥加密算法的安全性等价于随机数生成算法的安全性.因此,设计明文空间较小情况
下,抗后门攻击的对冲公钥加密算法,是一个值得探索的方向.
3 基于随机性强化的方法

本节讨论基于随机性强化的抗随机数后门攻击方法.目前,基于随机性强化的方法可以概括为 3 类,即
nonce-based 公钥加密算法(nonce-based public-key encryption,简称 N-PKE) [1,4,21,22] 、对冲的 nonce-based 公钥加
[5]
[3]
密算法(hedged nonce-based public key encryption,简称 HN-PKE) 、Dodis 随机数生成算法 .以下对这 3 种方
法分别进行总结.
3.1 N-PKE算法
Nonce-based 公钥加密算法的发展可以追溯到 2002 年,Rogaway 在关联数据的可验证加密方案中首次引入
[4]
了 nonce 的概念 [21] .2004 年,Rogaway 首次提出 nonce-based 对称加密方案 .2006 年,Rogaway 和 Shrimpton 细
化了 nonce 的概念 [22] .他们表示:packet sequence numbers 即可作为一个 nonce,并且强调 nonce-based 加密思想可
[1]
以有效抵抗随机数后门攻击.2016 年,Bellare 和 Tackmann 提出了 nonce-based 公钥密码算法 .
在文献[1]中,Bellare 和 Tackmann 定义了 nonce-based 公钥密码算法应满足的安全属性,并给出了具体构造
和安全性分析.相比于传统公钥密码算法,nonce-based 公钥密码算法中需要使用两个额外的密码组件,即 nonce
生成器(nonce generator,简称 NG)和对冲提取器(hedged extractor,简称 HE).
• 前者的输入为安全参数 k、nonce selector η和当前状态值 St,输出为 nonce 值 n 和下一个状态值 St′;
• 后者输入为安全参数 k,种子密钥 xk、消息 M 和 nonce n,输出一个随机数 r.
[1]
Bellare 和 Tackmann 分别给出了 HE 在随机预言模型和标准模型下的构造方法 .
在随机预言模型下 HE 的构造,需把 HE 看作随机预言机 RO.假设 k 是种子密钥的长度,l 是 HE 的输出长度,
*
*
k
l
HE.Keys={0,1} ,HE.Dom={0,1} ×{0,1} ,HE.Rng={0,1} ,其中,HE.Dom 是(n,M)的取值空间.HE 可定义为映射
*
RO
HE:HE.Keys×HE.Dom→HE.Rng.具体 HE 的构造为 HE (xk,(n,M)),其中,xk 为种子密钥,n∈{0,1} 为 nonce 值,
RO
*
M∈{0,1} 表示消息.为保证构造的安全性,HE 需视作 RO,即 HE (xk,(n,M))=RO((xk,(n,M)),l).
标准模型下,HE 的构造基于伪随机函数 PRF(pseudorandom function)和 AXUHF(almost XOR universal Hash
*
*
l
l
function).将 PRF 记为映射 F:F.Keys×({0,1} ×{0,1} )→{0,1} ,将 AXUHF 记为映射 H:H.Keys×H.Dom→{0,1} .其
*
中,F.Keys 和 H.Keys 分别表示 PRF 和 AXUHF 的密钥空间,H.Dom⊆{0,1} 表示 nonce 值的取值空间.假设种子密
*
钥为 xk、nonce 值为 n∈H.Dom、消息为 M∈{0,1} ,标准模型下 HE 的构造如下.
• 先将 xk 分为两部分,即 xk→(hk,fk),其中,hk 和 fk 分别属于 H.Keys 和 F.Keys;
• 分别执行 PRF 和 AXUHF,即 H(hk,n)→z 1 ,F(fk,(M,n))→z 2 ;
l
• 最终,HE 的输出为 z 1 ⊕z 2 ∈{0,1} .
[1]
Nonce-based 公钥加密算法基于一个传统安全的公钥加密算法设计 .下面介绍具体的 nonce-based 公钥加
密算法.为方便起见,我们将其记做 NPKE=(NKg,NSKg,NEnc,NDec),将所用的传统安全的公钥加密算法记为 PE=
(PE.Kg,PE.Enc,PE.Dec).一个 nonce-based 公钥加密算法包括如下 4 个基本算法.
k
k
k
• 密钥生成算法 NKg(1 ):输入安全参数 1 ,运行算法(pk,sk)←PE.Kg(1 ),输出公私钥对(pk,sk);