面向未来量子计算的新型多变量公钥密码关键技术研究

Public key cryptography system is a corner-stone of trusting in modern information age. Due to the emergence of quantum computers, study anti-quantum computing public key cryptographies to deal with the urgent security challenges of the information age.This proposal focuses on research multivariate public key cryptosystem, and our current focus is on the further development of more efficient and more secure multivariate public key cryptography system and realized it. The research-related issues,including:(1)building multivariate public key cryptosystem based on new mathematical ideas;(2)security analysis and provable security of MPKCs; (3)further development of odd characteristic construction and perturbation constructions;(4)pervasive computing devices optimized applications - Rainbow signature scheme. The research roadmap is top-down as follows: Designing next generation MPKCs with new algebraic methods;Security provability for all types of MPKCs; Combining two existing design methods for developing practical MPKCs; Optimizing Rainbow signature scheme for implementation of MPKCs. This proposal has the potential to lead to the development of new mathematical structures and methods, and will allow us to make contributions to areas beyond cryptography. Multivariable cryptography involved in this proposal will lead a significant impact on cybersecurity in quantum computing time and provide more options for us to protect our cyberspace.

公钥密码是网络空间信任链的基石。近两年来由于量子计算机研制步伐提速，对现有公钥密码系统带来了严峻的威胁。因此，研究新型公钥密码应对量子时代信息安全的挑战迫在眉睫。项目着眼于多变量公钥密码（MPKCs）研究，设计更高效安全的MPKCs。 研究内容：（1）运用新型代数方法设计新一代MPKCs；（2）分析和证明通用MPKCs的安全性；（3）结合并改进已有的内部扰动方法和奇数特征有限域方法，设计更安全高效的MPKCs；（4）对面向RFID应用的彩虹签名方案进行优化。 研究思路：采用"新方法设计新型MPKCs"→"通用MPKCs安全可证明性研究"→"改进现有方法设计实用MPKCs"→"面向MPKCs应用领域（RFID）的彩虹签名方案优化理论"的技术路线，对整体内容进行分层解构，同时各层研究重点之间相互衔接，形成从MPKCs设计理论到MPKCs实用化设计，由高到低，由基础到应用的研究框架。

为了应对量子计算机对现代密码技术，特别是公钥密码的巨大威胁，2015年8月美国国家安全局面向全球发布了即将采用新的后量子密码（PQC）来替换现有RAS/ECC公钥密码的公告。2016年2月美国NIST正式宣布启动PQC标准化工作。本项目于2015年1月正式立项，前瞻性的开展PQC家族当中多变量多项式公钥密码技术的研究。项目理论研究成果主要包括：（1）改进高效且可以抵抗秩攻击的简单矩阵（Simple Matrix）多变量公钥密码算法，用随机二次多项式作为矩阵元素得到三次方程组，提高算法的安全性。使得该方案在保持抵抗秩攻击的同时，密文明文长度比能灵活改变；（2）提出基于多变量公钥密码体制的门限环签名方案。利用公平划分思想，对一个环进行重复划分，每次划分成t个互斥的子环，形成一个(n,t) -完全划分系统。签名时，先计算各个子环的签名，再将这些签名连接起来，形成一个类环机制。该方案是一个关于多变量双极系统的门限环签名方案，满足门限环签名的正确性、匿名性要求。同时，在已知的关于多变量公钥密码的攻击下，新方案具备不可伪造性。成果（2）还在目前正在执行的一个国家级试点项目当中予以了成功的验证。本项目执行期间共发表论文7篇、获得党政密码科技进步奖、撰写专著两部（册）、申报并受理发明专利一项。尤为重要的是，在该项目实施期间开展了高水平国际合作交流，为我国在PQC科研领域搭建了良好的平台。目前国际上从事抗量子计算密码研究的两大顶级国际会议，ETSI量子安全密码国际会议和PQCrypto都（将）先后首次在中国举办，其中ETSI第六届量子安全密码国际会议已于2018年11月5日-8日在京举办；PQCrypto第十届国际会议将于2019年5月在中国重庆举办（www.pqcrypto2019.org），项目推动了我国在PQC国际标准化领域的合作，催生了亚洲抗量子密码论坛（AsiaPQC Forum）