实用后量子线性公钥加密的错误嵌入与通用构造

传统公钥密码不能抗量子攻击且大多速度慢难以应用于资源受限的计算环境，本项目研究抗量子攻击的线性公钥加密算法的新型设计理论与分析技术。内容包括：提出此类公钥密码的线性性安全度量工具，为线性公钥加密函数的设计提供更强的安全支撑，提出新的陷门单向函数，构造新的基于线性丢番图方程的公钥密码，证明该密码的抗格攻击安全性；定义新的困难问题，证明新问题与已有问题的规约关系，研究线性公钥加密的错误嵌入模式，构造新的实用公钥密码；研究具有错误嵌入的线性公钥加密函数特点，定义新的安全模型，提出通用安全构造方案，完成NTRU的可证明安全性；提出格上的子集最短向量问题，把子集和问题规约到该问题上，对STOC 2009上的基于稀疏子集和问题的Gentry同态加密算法进行攻击。该项目注重研究的可持续性和可移植性、理论和技术上的前瞻性及应用的有效性。研究成果将为具有线性结构的后量子公钥密码提供系统的设计理论和分析技术。

传统公钥密码不能抗量子攻击且大多速度慢难以应用于资源受限的计算环境，本项目研究抗量子攻击的线性公钥加密算法的新型设计理论与分析技术。内容包括：提出线性公钥加密的线性性安全度量工具，构造新的基于线性丢番图方程的公钥密码；定义新的困难问题，证明新问题与已有问题的规约关系，构造新的实用公钥密码；研究公钥密码底层数学问题的困难性，提出针对底层数学困难问题的攻击算法；构造基于格公钥密码的应用方案，完成方案的安全性和效率分析与比较。主要结果包括：提出一个新的线性公钥加密的密码原语：原像可选择陷门函数，并给出一个具体的构造，安全性分析指出，即使底层的紧凑背包问题是易解的，多项式时间的攻击者也不能攻破该算法的安全性；对Wang, Wu和Hu在2007年提出的一个概率公钥加密算法进行了改进，改进后的加密算法能够抵抗Youssef的和Lee的攻击；提出了具有双陷门解密机制的抗适应性选择密文攻击安全的公钥加密算法。引入了两个新问题，广义RSA问题和计算广义GSA问题，证明了标准RSA问题和广义RSA问题之间的等价性。基于计算广义RSA问题，提出了一个具有双陷门解密机制的公钥加密算法GenRSA。在随机预言机模型下，证明了GenRSA的抗适应性选择密文攻击的安全性；定义了模RSA数构成的四元数环上的求根问题并提出了一个数字签名算法，证明了该数字签名算法的安全性；提出了对背包公钥密码0/255的两种攻击，证明了使用连分式算法在多项式时间内恢复出背包公钥密码0/255在密钥生成过程中所使用的模乘数。证明了背包公钥密码0/255可以彻底攻破；通过背包公钥密码0/255的公钥可以构造一个格，而背包公钥密码0/255对应的私钥可以通过使用格规约算法寻找我们所构造出来的格上的最短向量重构出来；考虑了多变量公钥密码中的多项式线性等价问题(PLE)并讨论了PLE的相关密码学特性，给出了一个求解PLE问题的新算法：筛法，算法说明不能由PLE问题设计安全的多变量公钥加密算法；我们给出了F5算法的一个推广F5GEN，然后证明了F5GEN算法在有限步内终止，进而解决了F5算法的终止问题；构造了一系列基于格公钥密码的应用方案，包括线性同态签名算法、群组密钥协商协议、强指定验证者的格基签名算法、代理（重）签名算法、无证书加密算法等。研究成果丰富了线性公钥加密的设计理论，为后量子公钥密码提供系统的设计理论和分析技术。