量子计算环境下的格公钥密码体制

It has been realized for a long time that lattice-based cryptography is of great value.This project is devoted to studying two critical problems in lattice-based cryptography. (1) Trapdoors for lattices: simpler, tighter, faster, and smaller (STFS-trapdoors for short). (2) Security of lattice-based system in quantum computation setting. The mechanism of generating trapdoors and more ingenious cryptographic primitives for lattices will be explored so that we would have simpler ways for generating trapdoors with smaller size while keeping schemes provable secure. The security of STFS-trapdoors for lattices in conventional computation setting is also our focus, which includes security reduction, security proof, potential weakness of trapdoors, and novel attack methods. We will discuss the probability, security and space-time performance of using STFS-trapdoors to develop hierarchical/ broadcast/ homomorphic/ group lattice-based constructions while studying practical application schemes mentioned above in the standard model. We will focus on the secure proof of interactive lattice-based cryptographic protocol in quantum computation setting and the cryptoanalysis on lattice-based system available in the quantum-accessible random oracle model. Finding novel lattice-based cryptographic applications with the provable security in quantum computation setting is another aim. We are quite confident that, with the help of the Nation Science Foundation Project, we would do some outstanding work or make breakthroughs on cryptographic theory and key technology for lattice-based cryptography.

格公钥密码的普适价值早已被认识。本项目将研究格公钥密码的两个紧迫的"硬"课题：（1）格上STFS（simpler, tighter, faster, and smaller）陷门；（2）格公钥密码在量子计算环境下的安全性。 我们将进一步发掘基于格的陷门机理，探索更巧妙的密码原型，研究在可证明安全前提下显著降低陷门的空间尺寸和简单的陷门生成方法。我们将研究格上STFS陷门在传统计算环境下的安全性，包括安全归约和安全证明，并研究陷门的隐藏弱点，发掘新型攻击。我们将探讨格上STFS陷门应用于分级/广播/同态/群组的可能性、安全性和时空性能，并研究标准模型下的各种应用方案。我们将研究格上交互式密码协议的量子安全性证明，以及量子随机预言机模型下的格公钥密码安全性分析。我们将致力于寻找新的基于格的量子安全密码应用。希望借助本课题能在格公钥密码理论与关键技术上做出我们突破性的工作。

格公钥密码作为后量子密码的典型代表，其普适价值早已被认识。但其本身又具有庞大的空间尺寸、大量的实数精度计算、线性弱点等劣势。故本项目致力于研究格公钥密码的两个紧迫课题：格上STFS陷门及格公钥密码在量子计算环境下的安全性，进一步寻找新的基于格的量子安全密码应用。重要结果具体如下：.在密码原型的分析方面：对基于理想格的GGH映射以及基于GGH映射的众多密码体制进行有效的攻击。攻击结果表明，在编码工具公开时，GGH映射的所有密码应用不再安全；在编码工具隐藏时，至少有一个应用不安全。.在格上STFS陷门设计方面：提出新的高斯采样算法，并用于构造数字签名方案。.在量子计算环境下协议的安全性分析方面：给出了一个改进的量子计算环境下安全的身份认证协议；在量子敌手存在的环境下，分析了一个基于格公钥密码的OT协议的安全性。.在基于格的加密算法构造方面：在标准模型下利用混合加密的概念提出了一个构造KDM安全的非对称加密方案的新方法；基于RLWE困难问题提出一个限层全同态加密方案；利用原像抽样算法及LWE问题构造了格上无证书加密方案；基于LWE问题，设计了选择关键字不可区分的公钥加密方案。.在基于格的签名算法方面：在标准模型下构造了基于身份的可撤销的强不可伪造签名方案；用原像采样算法实现签名私钥提取，用抛弃采样技术完成签名，构造了格上高效的基于属性的签名方案；构造了NTRU格上的基于身份的签名方案；提出了一个基于NTRU格的有效的环签名方案；提出了一种基于格的新的非交互可否定环签名方案，该方案在量子攻击下被证明是匿名的、可追踪的和不可陷害的。.此外，基于格还设计了基于身份的可撤销的签密方案，基于格的OT协议等。以上成果不仅极大丰富了基于格的密码算法的多样化设计方法，还为将来面向物联网和云计算的高级别服务功能提供了密码理论的支撑。