基于格的密码技术与量子可证明安全理论研究

In August 2015, the American National Security Agency (NSA) released a major policy statement on the transitioning from traditional cryptographic algorithms to quantum resistant algorithms such as cryptosystems based on some lattice problems. However, the current research on lattice-based cryptosystems and the provable security against quantum adversaries poses a big challenge to the plan for transitioning to quantum resistant cryptosystems. This project follows the general framework of provable security, i.e., “Hard assumption—Security model—Security reduction”, and focuses on the research of lattice-based cryptosystems, the quantum security model and the security reduction against quantum computer adversaries, including (1) the security models for quantum computer adversaries that take account of the new inherent features of quantum algorithms; (2) the lattice-based cryptosystems that consider practical requirements; (3) the security reduction techniques for lattice-based cryptosystem in the quantum security model, and the strict security proofs for the proposed lattice-based cryptosystems. This project aims at providing both theoretical and technical supports to our nation’s plan for “transitioning to quantum resistant cryptosystems”, by solving some key issues in the provable quantum security, and mainly constructing several (identity-based) public-key encryptions, signatures, and key establishment protocols from lattices.

2015年8月，美国国家安全局(NSA)发布了“抗量子密码迁移计划”的通告，指出将逐步用基于格上问题等抗量子困难假设的密码方案来替代传统密码方案。然而，格上密码系统和针对量子计算机敌手可证明安全理论的研究状态却给实施“抗量子密码迁移计划”提出了巨大的挑战。本项目将围绕“困难假设—安全模型—安全归约”的可证明安全基本理论，对格上密码技术和针对量子计算机敌手的安全模型、安全归约展开系统研究，包括：(1)结合量子算法的新特性，设计准确刻画量子计算机敌手能力的量子安全模型；(2)紧贴实际应用需求，研究基于格上困难问题的密码技术和方案；(3)研究格上密码方案在量子安全模型下的安全归约技术，并为提出的密码方案给出严格的安全证明。通过项目研究解决量子可证明安全理论的关键技术，重点设计若干格上（基于身份）加密方案，签名方案和密钥交换协议，为实施我国的“抗量子密码迁移计划”提供理论依据和技术储备。

由于大整数分解和离散对数等传统的数学困难问题在量子计算机下存在多项式时间的求解算法，基于这些数学问题困难性并在实际应用中大规模部署的公钥密码系统将不能抵抗量子计算机敌手的攻击。特别地，近年来多个关键技术的突破已使得量子计算机不再遥不可及，研究和设计能够抵抗量子计算攻击的密码算法已经变得十分紧迫。事实上，美国国家安全局（NSA）已于2015年发布了关于Suite B密码算法的通告，宣布将逐渐用抗量子算法来替代现有Suite B密码算法的初步计划。2016年，美国国家标准与技术研究所（NIST）也启动了面向全球征集抗量子密码算法的抗量子密码标准计划。2018年，“抗量子密码算法设计”入选中国科协发布的60个重大科技难题，同年中国密码学会启动了全国密码算法竞赛，旨在推动我国新一代密码算法的发展。.课题组面向国家和社会对于抗量子密码算法的需求，围绕可证明安全的基本理论，对格上抗量子密码技术、量子安全模型和安全归约展开系统研究。具体地，课题组研究了密码方案量子安全模型及其与经典安全模型之间的关系、格上抗量子密码方案设计与分析技术以及格上问题困难强度的评估方法，给出了量子随机预言机模型和传统随机预言机模型的指数黑箱分离，揭示了量子随机预言机模型与经典随机预言机模型下的黑箱归约技术之间的关系，为在量子随机预言机模型下设计可证明安全的密码方案奠定了理论基础；解决了基于LPN问题抗量子密码算法研究的长期公开问题，突破了格上标准模型下选择密文可证明安全公钥加密方案的传统设计框架，给出了两轮口令认证密钥交换协议的通用构造。课题组共设计完成5个抗量子密码算法，编写完成针对格上ALWE和ASIS问题计算复杂度的自动化评估模型，为我国的抗量子密码研究和标准化提供了算法和技术储备。课题在重要会议和期刊上发表了学术论文13篇，申请了抗量子密码算法国家发明专利2项，获得了全国密码算法设计竞赛（公钥算法）一等奖2项。