基于格困难问题的公钥加密算法的设计与安全性证明

摘要

基于大整数因子分级和离散对数的传统公钥密码体制运算速度比较慢，这限制了它们的应用范围。随着量子计算的发展，基于新型困难问题密码算法设计的重要性被提升到了一个前所未有的高度。基于格困难问题的快速公钥算法是新型密码设计的一个重要方向，本文对此进行了研究，取得了如下成果： （1）给出了一条NTRU加密算法参数选择规则：要求NTRU的三个参数n，p，q满足分圆多项式∑n-1 i=0 xi在GF（p）和GF（q）上不可分解。此时，对于环R=Z[x]/（xn-1）的任意一个多项式f≠k∑n-1 i=0 xi（k∈Z），只要满足f（1）≠0，f在模p和模q意义下的逆一定存在。这不仅保证了密钥生成的效率，而且避免了弱密钥的产生。 （2）当NTRU的公钥h与Xn－1的在环R=Z[x]/（xn-1）上的最大公因式gcd（h，Xn－1）的次数不为零时，构造了一种类似于循环码译码的方法结合格基规约算法破解用h加密产生的密文。进一步的，若gcd（h，Xn-1）的次数为k，攻击者只需用格基规约算法求解（n-k）维格中的SVP问题即可得到明文。 （3）对三轮OAEP明文填充方案进行了分析，指出当攻击者可以获得填充方案中的随机串时，三轮OAEP并不能让RSA，ELGamal等加密算法达到适应性选择密文攻击下的语义安全性。对三轮OAEP进行了改进，使其在填充算法中随机串泄露的情况下仍然可以让加密算法达到适应性选择密文攻击下的语义安全性，并在随机预言机模型下证明了这个结论。 （4）为NTRU加密算法设计了一个明文填充方案。在加密算法选择适当参数保证合法加密不会发生解密失败的条件下，该填充方案能使NTRU达到适应性选择密文攻击下的语义安全性。与现有的NTRU明文填充方案NAEP相比，我们的填充算法更简洁更便于实现。 （5）提出了一种改进的NTRU加密算法。改进算法解密时能精确消除加密过程中所用的工作密钥，避免了像NTRU那样公钥所对应的CS格中任意足够短的向量都可以用来解密的情况。只有原密钥向量可以用来解密使得格基规约技术不能直接攻击改进算法，这是以计算量和密钥长度的增加为代价的。为改进算法设计了一种明文填充方案，并在随机预言机模型下证明了填充方案在适应性选择密文攻击下的语义安全性。

目录

文摘

英文文摘

论文说明：符号说明

声明

第一章绪 论

§1.1公钥密码体制研究现状

§1.2基于格困难问题的公钥密码研究现状

1.2.1基于格困难问题的加密算法

1.2.2基于格困难问题的签名算法

1.2.3基于格困难问题的公钥密码体制的可证明安全

§1.3本文的主要工作及内容安排

第二章格理论及其在密码学中的应用

§2.1格的基础知识

§2.2格基规约

2.2.1 LLL归约基的定义及性质

2.2.2 LLL规约算法

§2.3格理论在密码分析与设计中的应用

2.3.1格基规约在密码分析中的应用

2.3.2格理论在密码设计中的应用

第三章NTRU加密算法及其安全性

§3.1 NTRU加密算法描述

3.1.1参数选择及基本运算

3.1.2密钥生成

3.1.3加解密算法

3.1.4所基于的困难问题

3.1.5加密算法的可展性

3.1.6三个计算问题

3.1.7解密失败

§3.2对NTRU加密算法的攻击

3.2.1 E.Jautmes的选择密文攻击

3.2.2 John A.Proos的选择明文攻击

§3.3弱密钥及相应的简化攻击

3.3.1循环码的基本概念

3.3.2 NTRU的弱密钥及简化攻击

第四章随机预言机模型下的明文填充方案

§4.1.基础知识

§4.2几个著名的明文填充方案

4.2.1 OAEP和OAEP+

4.2.2 REACT

4.2.3 NAEP

4.2.4三轮OAEP

§4.3一种改进的三轮OAEP明文填充方案

4.3.1对OAEP3的攻击

4.3.2改进的OAEP3

§4.4 NTRU明文填充方案

4.4.1算法描述

4.4.2安全性证明

第五章改进的NTRU加密算法

§5.1 NTRU的两个变型算法

5.1.1 G-NTRU

5.1.2 MaTRU

§5.2 R-NTRU算法描述

5.2.1参数选择

5.2.2密钥生成

5.2.3加解密算法

5.2.4算法的可展性

5.2.5对格基规约攻击的分析

§5.3 R-NTRU的明文填充方案

5.3.1填充算法

5.3.2与NAEP和EPN的比较

5.3.3安全性证明

结束语

致谢

参考文献

攻读博士学位期间的研究成果