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

2890 Journal of Software 软件学报 Vol.32, No.9, September 2021

m = F K 2 ()r ⊕ c .
2
证明结果表明:在 P 是伪随机置换并且 F 是伪随机函数的假设成立时,上述方案满足 CRA 安全性.
SKE2 为抗随机数后门攻击的可变长度对称加密算法.SKE2 可以看作是 SKE1 的扩展算法,把消息空间扩展
到无限长度.具体的 SKE2=(Gen,Enc,Dec)算法介绍如下.
k
k
• 密钥生成算法 Gen(1 ):输入安全参数 k,该算法选取 K 1 ,K 2 ←{0,1} ,输出对称密钥 K=〈K 1 ,K 2 〉;
• 加密算法 Enc K (m,r):将要加密的消息 m 分为 l 个长度为 k 的分量,即 m=〈m 1 ,…,m l 〉.该加密算法输入
m=〈m 1 ,…,m l 〉、随机数 r←{0,1} 和对称密钥 K=〈K 1 ,K 2 〉.对于 1≤i≤l,计算 c = F K 2 (r i+ ) ⊕ m ,输出密文
k
i
i
C =〈 P ( ), ,...,r c c 〉 .其中,F 表示伪随机函数,P 表示伪随机置换;
K 1 1 l
• 解密算法 Dec K (c 1 ,c 2 ):输入密文 C=〈c 1 ,c 2 〉和对称密钥 K=〈K 1 ,K 2 〉,该算法计算 r = P − 1 ()c .对于 1≤i≤l,计
K 1 0
算 m = F (r i+ ) ⊕ c ,输出消息 m=〈m 1 ,…,m l 〉.
i K 2 i
证明结果表明:在 P 是伪随机置换并且 F 是伪随机函数的假设成立时,算法 SKE2 满足 CRA 安全性.
1.2 需要进一步研究的问题
到目前为止,关于抗随机数后门攻击的对称加密算法的研究成果并不多,较为有效的算法仅有 Kamara-
Katz 系列对称加密算法 SKE1,SKE2.但是我们不难发现,该算法的构造依赖于很强的假设条件.因为在算法实现
过程中,很难保证所用的 P 函数和 F 函数是真正伪随机的,所以除了伪随机函数和伪随机置换之外,还可以用哪
些数学工具和密码原语来构造抗后门攻击的对称密码算法,是一个需要研究的问题.另外,Kamara-Katz 系列对
称加密算法相当于重新构造了一个对称加密算法,而不是在现有对称加密算法基础上构造.如何构造实用的抗
随机数后门攻击的对称加密算法,即简单改变现有密码库(如 OpenSSL 库)的使用方式即可实现抗后门攻击,也
是此研究领域的另一重要的有待解决的问题.这将大大减少密码库开发者的工作量,节省开发成本.
2 对冲公钥加密算法 H-PKE

对冲公钥加密算法最早由 Bellare 等人在 2009 年亚密会(ASIACRYPT)上提出 [18] .所谓对冲是指密码算法满
足两个层次的安全性.
• 第 1 层安全性是指在加密算法中所用随机数是可靠的、高熵的情况下,算法可达到标准安全性(如
IND-CPA,IND-CCA);
• 第 2 层安全性是指在加密算法中所用随机数是不可靠的、低熵的情况下,算法依然可以满足某些比标
准安全性稍弱的安全性,而不是直接被攻破 [2,3,18] .
当对冲公开密钥加密算法同时满足上述两个层次的安全性时,才说它是对冲安全的.对冲加密算法要求被
加密的消息和加密时所用随机数的联合分布具有高熵.现有的对冲加密算法可以概括为 3 类,即确定性公钥加
密(deterministic public-key encryption,简称 D-PKE) [2,18−20] 、随机再确定性公钥加密算法(randomized-then-
deterministic,简称 RtD) [2,18] 、填充再确定性公钥加密(pad-then- deterministic,简称 PtD) [2,18] .本节讨论对冲公钥加
密的含义和安全性概念,然后分别从上述 3 个方面对现有方案进行总结和分析.
2.1 D-PKE算法
确定性公钥加密算法最早是由 Bellare 等人在 2007 年美密会(CRYPTO)上提出来的密码学原语 [19] .在文献
[18]中,作者指出,确定性加密算法是构造对冲加密算法的一种方法.所谓确定性加密,本质上是指在算法设计中
不使用随机数.他们指出,设计确定性公钥加密算法存在两个问题.
• 首先,如果一个敌手得知该算法的明文消息是从一个小的明文空间中选取的,那么他可以很容易用穷
举法恢复出明文.为解决这个问题,他们要求算法的明文空间足够大,并且具有高的最小熵;
• 其次,因为在确定性公钥加密算中不使用随机数,所以加密算法输出的密文在某种程度上暴露了明文
的部分信息.该问题的解决办法是要求明文不依赖于公钥,即明文和公钥是相互独立的.
文献[19]中提出了两个在随机预言模型下的确定性公钥加密算法实例:EwH 算法(encrypt-with-Hash,简称