后量子密码的发展趋势研究
后量子密码技术报告
引言
随着信息技术的快速发展，密码技术在信息时代发挥着重要作用。然而，量子计算机的出现对传统密码技术提出了严峻挑战。量子计算机的出现使得经典密码算法在多项式时间内可解决问题，如 Grobner 算法、Shor 算法和 Grover 算法。这些算法对 RSA、AES、ECDSA 等经典密码方案构成了威胁。因此，研究抗量子密码（Post-Quantum Cryptography，PQC）成为当务之急。
量子计算的发展
量子计算的崛起
量子计算的发展经历了从理论研究到实际应用的转变。2011 年，英国量子通信安全公司 (NIST) 发布了关于量子计算技术的白皮书，强调其在密码学中的潜在威胁。2012 年，美国量子计算中心 (NIST) 宣布启动 PQC 标准化计划，旨在制定抗量子密码标准。
摘 要
密码犹如维护网络安全的坚固屏障。量子计算的出现，使得传统密码体系在信息安全领域面临着严峻挑战。目前，后量子密码算法被认为是能够在量子环境下确保通信安全的新兴密码方案。基于现有量子计算技术及后量子密码方案设计的最新研究进展，我们对后量子密码研究的紧迫性进行了深入分析，并明确了其在信息安全领域的重要地位。最后，我们对后量子密码的未来研究方向进行了探讨，并为我国后量子密码技术的发展提供了理论参考。
内容目录：
1 量子计算机的发展现状
2 抵御量子威胁时不我待
2.1 抵御量子威胁的战略意义
2.2 密码算法的实用化需要时间孵化
3 全球守护量子时代下的信息安全
3.1 后量子密码理论的国际学术交流
3.2 后量子密码方案的标准化建立
4 后量子密码的构造方式
4.1 基于格的后量子密码算法
4.2 基于编码的后量子密码算法
4.3 基于哈希的后量子密码算法
4.4 基于多变量的后量子密码算法
4.5 其他后量子密码算法
5 后量子密码的发展趋势
5.1 经典后量子密码算法的优化与拓展
5.2 量子算法与密码算法的结合
5.3 密码算法量子安全性的评估
5.4 量子环境下新的数学问题探索
6 结 语
古往今来，从古代的飞鸽传书到现代的网络通信，在以知识经济为基础的信息化社会中，维护网络信息安全无疑已成为国与国之间无形的制胜法宝。在历史上，图灵发明了电子计算机，成功破译了密码机，从而打破了国家间信息安全的屏障。随后，在经典计算机上，人们基于数学上的NP难问题设计了加解密算法，维护了近50年的网络信息安全。然而，1982年，Feynman首次提出了将量子力学与计算机相结合的构想，开启了量子时代的先河。1985年，Deutsch进一步阐述了量子计算机的基本概念，并证实了在某些方面，量子计算机相较于经典计算机确实具有更强大的功能。1994年，Shor提出了能够在多项式时间内解决大整数分解和离散对数问题的量子算法。至此，人们才意识到在量子计算机面前，依靠现有密码技术构建的"安全堡垒"是多么脆弱。因此，研究能够抵御量子计算机攻击的下一代加密算法也变得刻不容缓。
1
量子计算机的发展现状
20 世纪后期，量子计算机作为一种融合了量子力学与计算机技术的创新成果，受到了国际社会的广泛关注。鉴于其战略意义，各国均给予高度重视，并持续加大研发与投入力度，通过制定专项政策、建立研究机构、启动科研项目等方式，共同推动量子科技的创新发展及其产业化进程。美国作为全球量子计算研究的领头羊，通过巨额投入的方式推动了该领域的重要计划。具体而言，美国政府设立了五个专门针对量子计算机的研究计划，包括由美国国防高级研究计划局主导的“量子信息科学与技术发展规划”，由美国国家安全局指导的ARDA5计划，依托美国科学基金会的QuBIC计划，由美国宇航局领导的QCTG计划，以及由美国国家标准与技术研究机构指挥的PLQI计划。此外，欧盟、加拿大、中国等国家和地区也在量子计算机研究领域积极布局，取得了显著的科研成果。
2001年，IBM公司成功研制了具有7qubit功能的量子计算机，首次处于该领域研究的领先地位。2007年，中国科学家潘建伟在量子计算机上率先实现了Shor量子分解算法，这一成果标志着我国在光子量子计算机领域的国际研究水平已达到先进地位。2008年，加拿大D-wave公司成功提升了现有量子计算机的运算位数至48qubit。2010年，英国布里斯托尔大学研发出新型光子芯片，其运算速度更快，存储容量更大，为量子信息存储提供了全新思路。同年，潘建伟团队与清华大学合作开展研究，成功实现了全球最远距离的量子通信，并发表于国际权威期刊《Nature Photonics》，该成果展示了基于量子计算机的量子通信网络实现可行性。与此同时，杜江峰教授在《Nature》发表了一篇关于固态自旋比特量子相干性研究的论文，为固态自旋量子计算机的实现提供了重要理论支持。后来，英国和澳大利亚的研究团队提出了“容错量子计算”（FTQC）方案，这一方案的提出为量子计算机走向实用化奠定了基础。
随着量子计算技术与硬件设备材料的飞速发展，人们愈发坚信量子计算机走向现实欠缺的不再是技术原因，而是时间的沉淀，借此各国加快针对量子计算机的研究脚步。2016 年，中国在“十三五”规划中明确设立关于“量子通信与量子计算机”的重大科研项目 。同年，Shor 量子分解算法成功运行在潘建伟团队研究的光量子计算机上，为纪念这一研究成果，发射了国际上第一颗名为“墨子号”的量子卫星。2017 年，潘建伟团队自主研发的 10 bit 超导量子线路样品成功实现了当时世界上最大数目的超导量子比特纠缠和完整测量，在量子计算机的发展道路上又迈上了一个新的台阶。2018 年，欧盟正式启动“量子技术旗舰计划”，该计划拟在欧洲建设一个连接所有量子计算机、模拟器与传感器的量子通信网络 。2019 年， 谷歌团队在量子计算原型机“悬铃木”上仅用了3 分 20 秒就完成了超级计算机一万年计算量的工作，该成果将量子计算机的处理能力又带向新的高度，一定意义上实现了量子霸权。2020年，美国白宫网站发布的《美国量子网络战略构想》提出，开发一种由量子计算机和其他量子设备组成的量子互联网的设想，并指出下一步的工作是使量子信息科学全民化。2021 年，中国提出了新的“十四五”规划，指出这 5 年是中国量子技术实现“弯道超车”的关键时期，其目标之一就是研制通用量子计算原型机和实用化量子模拟机 。同年 10 月，潘建伟团队与其他研究机构合作，成功构建了 113 个光子 144 种模式的量子计算原型机“九章二号”，实现了在高斯玻色取样数学问题上的快速求解。除此之外，潘建伟团队及其合作伙伴还成功研制出了66超导量子比特的“祖冲之二号”，相比于“悬铃木”，在计算复杂度方面提高了 6 个数量级。2022 年，Huggins 等人在 Nature 上发表文章，将 QMC 方法与量子计算相结合，构建了混合量子经典计算模型，提供了一条实现实际量子优势的途径，为实用化量子计算机的设计提供了理论基础。
量子计算机的快速发展降低了处理速度，成功解决了众多复杂的数学问题，给当前广泛使用的现代公钥密码体制带来了显著威胁和严峻挑战。然而，保障网络安全与信息系统安全的关键在于密码技术的发展，因此，在量子信息时代到来之前，设计能够抵御量子计算机攻击的新型密码体系，成为密码学家们迫在眉睫的任务。
2
抵御量子威胁时不我待
2.1 抵御量子威胁的战略意义
密码技术承担着维护信息安全的核心保障作用，广泛应用于国家保密系统和大型国防装备。当量子计算机技术发展成熟时，基于大整数分解和离散对数问题的现代公钥密码体系将面临被破解的威胁，这直接关系到党政军民各领域网络信息安全的稳定性，甚至可能对国家安全构成更深远的影响。
在军事领域，“先储存后解密”是一种破解当前密码系统的重要战略方针，即一些组织将无法解密的信息先储存起来，待机件成熟后进行解密。基于“摩尔定律”的发展规律，成熟的时间窗口可能需要极长的时间才能出现，而量子计算的出现，加速了这一成熟过程，对长期保密性和前向安全性构成了致命威胁。在国家军队和许多关键机构的设备中， storing了大量国家安全情报，这些情报需要保存超过十年以上的时间而不受破解。由此可见，量子计算的出现将直接威胁到国家重要情报的安全，因此，研制能够有效抵御量子计算机攻击的新一代加密体制迫在眉睫，以最大限度地消除这一隐患。
在日常通信领域，关键的通信协议主要依赖于公钥加密、数字签名和密钥交换技术。然而，这些公钥密码学算法的安全性依赖于某些数论难题的求解难度，但这种挑战在量子计算时代显得微不足道。量子计算的普及将使这些传统通信协议的安全性受到严重影响，传统的端到端通信安全将无法得到保障。
2.2 密码算法的实用化需要时间孵化
任何一个密码算法的设计都旨在迁移到工程化应用中。从现代密码算法的理论技术发展成熟到最终实现标准化，大约耗时20年，才构建完成一套完整的公钥密码基础设施系统。即便新型密码算法的理论技术已具备成熟性，将现有多用密码系统逐步演变为能够抵御量子计算机攻击的新型密码系统，这一过程同样需要大量时间，而现有多用的抗量子密码系统理论技术尚未成熟。因此，无论量子时代何时降临，尽快启动新型密码方案的设计工作，以确保量子计算机信息与通信系统的安全，都是势在必行的。
3
全球守护量子时代下的信息安全
借鉴经典计算机中设计公钥密码算法的思路，目前，国际上针对量子计算机威胁的PQC算法研究主要集中在寻找一类或多类在量子计算环境中无法在多项式时间内解决的数学难题。基于这些数学难题设计的PQC算法能够在一定程度上抵御量子计算机的攻击，保障量子信息时代下的通信安全。全球对PQC算法的研究主要集中在两个方面：国际学术交流和算法标准化建设。
3.1 后量子密码理论的国际学术交流
在密码学领域中，国际PQC理论和技术研究一直受到包括英美在内的广泛关注，相关学术交流活动数量和频率持续上升，其影响范围正向更多国家及新兴领域延伸。
2006年，密码学研究协会首次举办全球性后量子密码技术会议，该会议深入探讨了PQC未来可能面临的挑战。会议之后，该活动在北美、欧洲和东亚地区连续举办，并通过在相邻会议之间举办夏季或冬季培训营的方式，促进了各国研究者之间的交流，并推动了PQC技术的进一步发展。
2011年，美国安全创新公司成立并获得了NTRU算法的专利，随后该公司开发了多种基于NTRU算法实现的软件库。2013年，欧洲电信标准协会与加拿大滑铁卢大学量子计算中心联合举办了量子安全密码工作组会议（IQC/ETSI Quantum-Safe Crypto Workshop），会议吸引了来自密码学、数学、物理学、计算机等多个领域的研究者，目标是制定下一代密码标准，以应对量子计算带来的挑战。2015年1月，欧盟启动了PQC算法SAFECRYPTO应用项目。通过欧洲多家企业、高校和研究机构的协作，项目成功开展了PQC项目和PROMETHEUS项目，并将其纳入欧盟地平线2020计划，致力于开发新一代安全实用的PQC方案。2016年4月，微软公司开发出了基于格上的困难问题RLWE的格密码库（Lattice Crypto），该库声称即使攻击者使用经典计算机或量子计算机，也能实现至少128位的安全性能。同年7月，谷歌公司宣布将开始开展PQC技术的测试工作，并将测试重点放在基于RLWE问题的密钥交换协议上。2019年1月，谷歌宣布将部署一种名为组合椭圆曲线和后量子密钥交换（CECPQ2）的新型传输层安全性协议（Transport Layer Security，TLS）密钥交换方法。同时，谷歌与Cloudflare合作探索PQC技术在如何击败超文本传输安全协议（Hypertext Transfer Protocol Secure，HTTPS）连接方面的应用潜力。2022年4月，IBM公司发布了首个基于格理论研发的量子安全系统——IBMz16。
亚洲密码学研究者对后量子技术的发展始终保持高度关注。2016年6月，首届亚洲后量子密码论坛（PQCAsia Forum）在成都顺利举行。基于PQC算法的快速发展，原计划于2017年召开的第二届亚洲后量子密码论坛因故推迟至2016年11月在韩国首尔大学举办。2020至2021年间，由丁津泰领导的团队成功解密了两个被美国国家标准与技术研究所（NIST）采纳的抗量子数字签名候选方案，包括Luov和GeMMS，并在2020年欧洲密码学年会以及2021年美国密码学年会上发表了相关研究成果。2022年，上海交通大学谷大武教授领导的LoCCS实验室在解决80维格的容错学习问题（Learning With Errors，LWE）方面取得了突破性进展，将这一成果正式登载于格密码领域官方的挑战网站LWE Challenge。
3.2 后量子密码方案的标准化建立
目前，全球已有多个国家认识到未来量子攻击可能对网络安全构成潜在威胁，并已采取相应的行动和相关措施来应对这一威胁。与现代密码学中使用的DES、AES、RSA、ElGamal等加密算法标准类似，在PQC理论研究中，标准化工作逐步发展起来，越来越多的国际社会成员纷纷加入PQC方案标准化工作的研究中。
3.2.1 美国后量子密码标准化计划
早在2008年，NTRU加密算法就被美国电气和电子工程师协会正式确定为标准（Std1363.1—2008）。随后，该标准在2010年又被国际认可标准委员会（Accredited Standards Committee X9）批准为适用于数据防护的新型加密方案。同时，美国国家标准学会X9.98标准（ANSI X9.98）则明确规定了在金融交易过程中如何将基于NTRU等格加密算法的公私钥系统应用于实际操作中。
2015年8月，美国国家安全局宣布对当前美国政府所使用的“密码算法B套件”进行安全性升级，升级的算法将被用于后量子时代过渡期的加密标准。2016年4月，NIST发布了“后量子密码学”研究报告，并启动了PQC算法标准计划。截至2017年底，NIST共收到了来自全球的82份候选密码方案，由此开启了后量子密码学标准协议的第一轮预选。2019年1月，NIST公布第二轮的标准方案，共有26个密码方案脱颖而出，其中包括17个公钥加密/密钥交换方案和9个数字签名方案。从构造方式来看，这26个候选算法中包括12个格密码，7个基于编码的密码，4个基于多变量的密码，2个基于哈希的密码和1个基于同源曲线的密码。2021年1月，NIST公布第三轮候选算法，其中包括7个决赛入选方案和8个备选方案。在7个决赛入选方案中，有5个是格密码，这表明格密码在所有PQC算法中占据主导地位，是未来最有希望成为标准化的算法。2022年3月，麻省理工学院与阿布扎比技术创新研究所合作编写并出版了《从今天起，直面明天的量子黑客》（Facing Tomorrow’s Quantum Hackers Today）。该报告对全球量子计算公司中的密码学家、数学家、物理学家和高级管理人员进行了采访，评估了一台成熟的量子黑客计算机对当前网络安全系统威胁与影响，并在此基础上分析了应对威胁的解决方案。这意味着NIST标准化即将进入第四轮。2022年7月，NIST已完成了第三轮PQC标准化过程，共有4个候选算法被选中标准化，分别是CRYSTALS-KYBER、CRYSTALS-Dilithium、FALCON和SPHINCS+，另外还有4种算法将继续进入第四轮。这一里程碑事件意味着持续6年的标准化工作终于进入了最后阶段。
3.2.2 欧洲后量子密码标准化计划
首先，在NIST-PQC算法征集过程中，欧洲研究团队在NIST发布的第二轮26个标准方案中发挥了关键作用，主导和参与的项目多达20多个。其次，2015年，欧洲量子密码学术界与工业界联合组织PQCrypto发布了一份初始报告，该报告在加密算法、对称授权和签名系统等多个领域提出了标准化建议，并明确指出McEliece密码系统具有成为替代RSA/ECC密码系统的潜力。此外，欧洲电信标准协会ETSI设立的“量子安全密码工业标准工作组”主要负责PQC算法的征集、评估与工业标准的制定工作，该组织每年发布一本《量子安全白皮书》，全面介绍后量子密码研究的最新动态。
3.2.3 日本后量子密码标准化计划
为应对量子计算攻击和对加密设备的物理性威胁（如功率分析攻击），日本启动了CREST密码数学研究项目，旨在为下一代加密系统构建技术基础。CREST项目每年举办后量子安全相关会议，为日本领域的后量子密码研究者提供交流平台。在PQC标准正式发布前，日本密码研究与评估委员会发布了三个密码清单，包括电子政务推荐密码清单、候选推荐密码清单以及监控密码清单，并明确指出将启动最新制定的PQC指南。
3.2.4 韩国后量子密码标准化计划
为及时跟进国际后量子标准化工作，韩国于2022年推出了全球首个具备防御能力的抗量子攻击专用量子计算专线，目前该线路已通过电信技术协会的测试与验证。
3.2.5 中国后量子密码标准化计划
相较于其他国家而言，中国在PQC标准化研究方面起步较晚。但在NIST-PQC算法征集活动中，中国积极参与并为该标准贡献了重要力量。参与设计的团队主要由密码科学技术国家重点实验室、上海交通大学、复旦大学、中科院信息工程研究所以及位于中国台湾地区的中央研究院等组成。其中，由中科院信息工程研究所设计的LAC算法，与欧洲、美国、加拿大等国家提供的PQC算法一道，成功入选了NIST第二轮PQC密码算法名单。此外，在国内PQC算法标准的征集活动中，中国也付出了努力。自2019年起，中国密码学会（CACR）设立了全国密码算法设计竞赛，该竞赛专为中国的密码学家开放，吸引了众多参赛者，并在公钥密码组中收集了大量PQC算法。该竞赛的成功举办不仅推动了我国密码理论的发展，也促进了应用技术的进步。这一竞赛在PQC标准制定过程中发挥了基础性作用，表明我国PQC技术正逐步向国际先进水平看齐。通过充分调动国内各界的研究资源，我国致力于推动国产化研发进程，以保障未来在量子计算时代的网络空间安全。
综上所述，各国政府在该领域投入的资源与支持力度显示，在量子信息真正时代到来之前，各国均致力于在量子通信网络中实现保密通信与安全认证。
4
后量子密码的构造方式
在PQC算法的设计方案中，主要依据是数学困难问题的不可解性。目前，主流的数学困难问题主要包含格、编码、哈希函数以及多变量问题。此外，基于超奇异椭圆曲线、量子随机漫步等技术构建的PQC方法，以及采用较大密钥长度的对称密码算法也被认为是量子计算环境下相对安全的方案。
4.1 基于格的后量子密码算法
格（lattice）是一种重要的数学结构，由一组线性无关的非零向量（称作格基）的整系数线性组合所定义。具体而言，给定一组格基，可以生成一系列具有特定性质的点集，这些点集在几何和数论中具有广泛的应用。
对任意的整数
均属于该格的向量，其中，n被定义为格的维度。对于同一格而言，可能存在多种格基，而求解格中最短向量问题（Shortest Vector Problem，SVP）以及最近向量问题（Closest Vector Problem，CVP）在当前格理论中被认定为主要的非确定性多项式复杂度难题（NP）。此外，格中还存在若干其他的重要难题，例如LWE问题、有限距离解码问题、小整数解问题以及gap-SVP问题等。基于此，格基算法在现代密码学中扮演着关键角色，它们不仅为公钥加密提供了实现基础，还被广泛应用于加解密、数字签名、属性加密、同态加密以及密钥交换等多种密码学构造。
1997年，Ajtai等人提出了基于格的第一代密码体制，即Ajtai-Dwork方案。该方案通过将格问题的最坏情况转化为平均情况来抵御量子计算的攻击。1998年，Hoffstein等人提出了NTRU公钥加密体制，该方案不仅成功入选NIST第三轮公钥加密标准候选名单，而且已成功应用于某些商用密码设备，预计未来将取代RSA加密算法。
在后量子时代下的加解密算法领域，通过对现有格密码方案进行归纳总结，我们发现基于LWE困难问题的格密码体系不仅具有广泛的适用性，而且其安全性优势更为显著。以NIST第四轮推荐的CRYSTALS-Kyber算法为例，该体系的困难基础是M-LWE问题，即结合了LWE和R-LWE两种问题，相较于单独的LWE问题而言，该体系具有较为容易扩展和计算效率较高的特点。M-LWE问题的核心理念在于对于多项式环
中均匀随机选取的
与经过公式
计算得到的
是不可区分的，其中
中
s 和
是从二项分布
中随机均匀选取的，该问题的主要困难性在于根据已知
无法计算 s 和
中的任意一个。Kyber 算法就是利用此原理，通过公式
生成公私钥对 (t,s)，确保已知公钥 t 后无法推导出私钥 s，随后对该通信系统的明文信息进行加密或对临时会话密钥进行封装。基于2020年最新版的Kyber算法，表1详细阐述了在选择明文攻击场景下实现IND-CPA安全的具体思路，而表2则展示了在自适应选择密文攻击下实现IND-CCA2安全的实现方案。
表 1 Kyber 算法实现过程（IND-CPA 安全）
表 2 Kyber 算法实现过程（IND-CCA2 安全）
在后量子签名算法领域，基于格的签名方案的构建方式与传统公钥密码体制存在显著差异。对于RSA、ElGamal、椭圆曲线等基于传统公钥体制的加密方案而言，通过交换加密与解密操作的公钥与私钥顺序，即可将这些传统公钥体制转换为对应的数字签名方案。然而，与基于格的密码方案不同，这类系统不具备上述对偶性，在设计基于格的后量子签名算法时通常需要采用零知识证明协议来进行构建。具体而言，证明者需展示其私钥与对应身份认证的公钥匹配，同时完全避免泄露任何关于私钥的具体信息。
在2008年，Gentry及其团队开创性地提出了一种名为GPV的框架，该框架系统性地阐述了基于晶格的数字签名方案的设计思路，如表3所示。
表3 GPV 框架
基于GPV框架的格签名算法在公私钥对生成过程中所依据的困难问题与LWE问题、SIS问题具有相似性。为了便于实现签名算法，设计过程中，通常会采用NTRU格来具体实现GPV框架，并通过采样机制完成数字签名的生成。例如，FALCON算法作为NIST第四轮候选方案之一，具有较高的竞争力。另一个备受关注的格签名方案，即CRYSTALSDilithium，也成功进入了NIST第四轮候选名单。
在设计过程中，CRYSTALS-Dilithium和FALCON两个算法分别针对算法安全性和运行速度进行了改进。CRYSTALS-Dilithium签名算法采用Fiat-Shamir with Aborts技术，通过拒绝采样使基于格的Fiat-Shamir方案更加紧凑且安全。为解决高斯采样难以高效实现的问题，Dilithium改进采样方式，仅依赖均匀分布采样完成签名创建。同时，Dilithium通过分离高低阶位降低了公钥大小，缩小了两倍以上。FALCON签名算法则在采样过程中应用快速傅里叶采样技术，并采用真正的高斯采样器，确保无限签名情况下密钥泄露可忽略。此外，FALCON的快速傅里叶采样在实现中显著提升了签名生成速度，每秒可达数千个，验签速度比其他算法快约5~10倍。关于Dilithium和FALCON的具体改进过程，可参考表4和表5。
表 4 Dilithium 签名算法的实现过程
表 5 FALCON 签名算法的实现过程
格密码的研究起步相对晚一些，尽管其结构简单，但其面临的众多高复杂度的数学难题却使其在后量子时代吸引了全球学者的目光。从2013年开始，格密码研究的显著成果不断涌现，随着基于格的密码体制不断改进，密钥尺寸持续缩小，运算速度持续提升，其在安全性、密钥尺寸以及计算速度方面逐步实现了更好的平衡。2022年7月，NIST第四轮的后量子密码中被选中3个基于格设计的密码方案，足以说明尽管格密码仍处于发展阶段，但目前其被认为是后量子密码算法中最有前景的方案之一。
4.2 基于编码的后量子密码算法
编码理论是数学与计算机科学的一个重要领域，专门用于在噪声信道中处理信息传输中的错误。基于编码的密码体制也被视为在量子计算机环境中相对安全的密码算法，其关键在于在编码中增加一定数量的错误码字，使得纠正错误码字或计算其伴随式的校验矩阵变得困难。
一种自1978年以来一直沿用的基于编码的公钥加密算法是 McEliece[27] 提出的 ClassicalMcEliece 方案。该方案采用随机二进制不可约的 Goppa 码作为私钥 A，并通过可逆矩阵 S 和随机置换矩阵 P 进行 A'=SAP 变换，生成公钥的一部分即为 A'。 McEliece 公钥加密方案的公钥由 Goppa 码的汉明重量 t 和矩阵 A' 构成，而私钥则由生成矩阵 A、可逆矩阵 S 和随机置换矩阵 P 组成（如图 6 所示）。该方案的安全性建立在对称群隐藏子群问题的基础上，即在加密过程中对明文信息 x 进行 y=y'+e=x×A'+e 的操作后，从带 t 个错误的向量 e 中反推出 Goppa 码是极其困难的。相较于现有公钥密码体制， McEliece 方案具有较快的加密速度，但其公钥尺寸过大，限制了其在实际应用中的推广。然而，经过对其的改进后，该方案最终成功进入 NIST 的第三轮候选算法。
表 6 McEliece 公钥加密方案过程
随后，1986年Niederreiter通过基于GRS码构建了一种背包式的公钥密码体系，即Niederreiter密码方案。该方案与McEliece密码方案的主要区别在于，Niederreiter方案在密钥生成阶段采用可逆矩阵M和置换矩阵P，通过A'=MHP操作隐藏校验矩阵H，而非直接生成生成矩阵A，从而构造公钥A'。为了验证Niederreiter密码方案的安全性，1994年，王新梅团队展示了该方案的安全性与McEliece密码方案具有等价性。
针对基于编码的数字签名方案而言，王新梅在1990年首次提出了基于编码的Xinmei数字签名方案。随后，李兴元提出了具有签名、加密和纠错能力的公钥体制模型。学者们在此基础上进行了进一步的完善，并指出，基于编码的公钥密码体制可能成为基于数论的公钥密码体制的一个有效替代方案。
4.3 基于哈希的后量子密码算法
基于哈希函数设计的后量子密码算法主要关注于数字签名算法领域。哈希函数具有的抗冲突性特征，使得当其展现出抗强冲突特性时，基于其构建的数字签名算法能够有效抵御量子计算的攻击。在哈希函数驱动的数字签名算法中，最具代表性的当属1989年Merkle提出的基于一次性签名方案的Merkle数字签名方案（MSS）。MSS的核心思想在于通过Hash树结构将多个一次性验证密钥（Hash树的叶子节点）的有效性降低至其根节点的公钥有效性。由于其卓越的抗冲突性能，MSS成功地抵御了量子计算的攻击，因此受到学术界的广泛关注。自2006年第一届国际后量子密码会议开始，针对MSS的改进方案不断涌现。例如，2006年Szydlo提出了一种优化Merkle树构建方法，使其更加高效实用；2008年基于Szydlo算法，Buchmann等人提出了一种改进数字签名机制认证路径的方法，显著降低了最坏情况下的算法运行时间；2011年，Buchmann等人在MSS基础上发展出一种更短签名的可证明安全XMSS数字签名方案。
在MSS研究之外，2016年，Targhi等人估计得出了寻找一个函数碰撞的量子查询复杂度。2017年，SPHINCS+算法被提交参加NIST PQC竞赛，最终成功进入该竞赛的第三轮候选名单。在进一步的安全性评估中，该算法在第四轮评估中脱颖而出，最终成为第四轮的候选签名算法之一。SPHINCS+签名算法采用了一种称为SPHINCS超树的结构进行构建，这种超树结构介于Merkle树和Goldreich树之间，其外层结构则是一个k叉树。
具体来说，该算法由 d 层组成，其中每一层都构成一个高度为 h' 的 Merkle 树结构。每个节点都对应一个密钥体系，其中叶子节点负责为子节点生成公钥，而非叶子节点则用于生成 FORS 密钥。值得注意的是，外层结构的叶子节点同样遵循 Merkle 树机制，用于对消息进行签名处理。SPHINCS+ 签名方案利用伪随机数生成器和预设种子构建一个 SPHINCS 超树结构。在实际签名操作中，首先计算消息 m 的哈希值 H(m)，然后从该哈希值中提取 h 个比特位来确定具体的 FORS 密钥应用。随后，再从哈希值中提取 kα 个比特位用于执行 FORS 签名过程。最终，SPHINCS 超树从叶子节点到根节点的签名链即为消息 m 的完整数字签名。在验证环节，接收方需逐一核查签名链中的每一个签名，确保其符合预期的结构和有效性。
尽管目前基于 Hash 函数的数字签名方案的成果尚不显著，但鉴于 Hash 函数的独特属性及其实用性，在量子时代，基于 Hash 函数的签名算法有望成为最具前景的数字签名方案之一。
4.4 基于多变量的后量子密码算法
在后量子密码算法的发展历程中，本方案处于领先地位。相较于其他主流构造方案，本方案在研究深度和广度上均显突出。采用有限域上一组二次多项式作为公钥映射，其安全性建立在求解有限域上非线性方程组的NP难性基础之上。
起源于1988年，多变量公钥密码体制最初由Matsumoto等学者提出。随后，清华大学丘成桐数学科学中心的丁津泰、日本的Kohtaro Tadaki以及我国台湾地区的Bo-Yin Yang等众多知名学者在该领域展开了深入讨论，并取得了显著的研究成果。近年来，学者们主要聚焦于三个关键方向：对加密、签名等方案中基本理论的深入研究和优化改进；对类似全同态加密（Fully Homomorphic Encryption，FHE）等前沿领域的重点攻关；以及对全新算法设计结构的探索与尝试。统计数据显示，在全八届国际后量子密码会议收集的论文中，约39%的论文是针对多变量密码算法的设计与改进[36]，这一比例远高于其他设计方式的后量子密码算法，充分体现了多变量公钥密码体制在后量子时代的重要地位与应用价值。
在众多多变量公钥密码体制中， Rainbow数字签名算法是丁津泰教授于2005年提出的进入NIST第三轮的多变量签名算法的一种。该算法通过采用相对较小的有限域和基础的逻辑运算实现了较高的运算速度。同时，该算法相较于其他签名算法因其较短的签名长度在实用性上更为突出。该算法采用非平衡油醋（Unbalanced Oil and Vinegar，UOV）体制创建签名，核心是一个多层的UOV结构的中心映射。UOV体制是油醋（Oil and Vinegar，OV）体制的一种扩展，OV体制在签名过程中，随机选取一组醋变量代入油醋多项式中，而UOV体制则是一种多层的油醋体制，每一层都是油醋多项式，且上一层的所有变量成为下一层的醋变量。Rainbow数字签名算法的具体流程如表7所示。
表 7 Rainbow 数字签名算法的实现过程
Rainbow签名算法自1999年以来一直面对多种密码攻击，包括MinRank类型的攻击、HighRank攻击以及Billet-Gilbert攻击等。直到2022年，Beullens对Rainbow签名算法进行了进一步的改进，表明其针对NIST第二轮提交的SL1参数集公钥的密钥恢复攻击方法，平均在53小时内即可恢复相应的密钥。
尽管多变量公钥密码体制未被NIST第四轮标准化候选名单所采纳，但在那些对算法效率要求较高的应用场景中，该技术仍可能展现出更高的性能水平。
4.5 其他后量子密码算法
除上述4种主流算法外，基于量子密码和基于同源的密码体制也在密码学家的研究范围内。2012年，Kashefi等人提出了量子单向函数的候选方案，Mosca等人对经典认证密钥交换框架下量子密钥的分配问题展开了研究。2006年，Couveignes引入了困难的同质空间（Hard Homogeneous Spaces，HHS）的概念，并进一步拓展了相关理论，为基于椭圆曲线同源的密码系统奠定了基础。同年，Rostovtsev等人提出了一个新的适用于公钥密码系统的通用数学问题：对于有限域上的椭圆曲线，计算给定椭圆曲线之间的同源（代数同态），同时ElGamal公钥加密和Diffie-Hellman密钥交换协议也被引入用于同源密码系统。2014年，Jao等人公布了一个基于椭圆曲线同源的不可否认数字签名方案。2017年，Gélin等人和Ti分别对超奇异同源密码系统的循环终止故障攻击和第一类故障攻击进行了深入讨论。2022年，Castryck、Maino和Chi-Domínguez分别提出了针对超奇异同源密钥交换协议（SIDH）的不同密钥恢复攻击方案。尽管这些后量子密码算法并未像其他主流算法那样形成完整的体系，但在未来，这些算法或新的后量子算法仍有潜力逐步进入密码学舞台。
5
后量子密码的发展趋势
量子计算机的出现标志着新一轮科技革命的开启。作为计算机领域的重要发展方向，量子计算机在密码破解、机器学习、量子模拟等多个领域展现出显著优势。其应用前景将逐步融入人们日常生活。后量子密码方案作为一种应对量子计算威胁的新型加密技术，其研究时长不过30年，仍有许多亟待解决的问题。
5.1 经典后量子密码算法的优化与拓展
量子计算的进步对密码技术提出了更高的要求，同时也推动了密码分析技术的发展。尽管目前已经设计出多种类型的后量子密码算法，但针对这些密码算法的理论攻击仍然存在，例如面向 NIST 第三轮入选算法中 Kyber 的密钥不匹配攻击等。因此，未来对已有的后量子密码算法的改进之路仍需继续前行。此外，针对算法的实用化改进同样具有重要意义。通过不断优化算法的参数设计，提高算法的运行效率，降低算法的时间复杂度和空间复杂度，使算法在实际应用中发挥作用。
5.2 量子算法与密码算法的结合
量子算法的主要目标是解决特定类型的问题并提高运行效率，例如，Shor算法的提出成功解决了大整数分解问题，而Grover算法显著提升了搜索速度。Simon算法的出现则为解决函数周期性问题提供了有效的方法。研究新型算法的构建，一方面，将量子算法应用于后量子密码的设计中可以显著提升算法的运行效率并增强其可用性；另一方面，将量子算法应用于密码分析方法中可以从一定程度上发现算法潜在的攻击可能性并调整算法参数，从而提高算法的安全性。
5.3 密码算法量子安全性的评估
在量子计算领域，已有的某些算法已被证明对经典密码体系存在有效的理论攻击。针对后量子密码体系而言，这种攻击是否同样有效目前尚不明确。此外，新的量子算法的出现是否会威胁现有后量子密码体系，这一问题同样未有定论。因此，评估密码体系的量子安全性将是一个未来的研究方向。
5.4 量子环境下新的数学问题探索
除了目前以格、哈希、多变量、编码为基础的后量子密码算法外，深入研究基于同源曲线或量子随机漫步的后量子密码算法也是十分必要的。此外，探索在量子计算优势之外的数学困难问题也是一种创新的研究方向。
6
结 语
针对量子计算的发展，美国已进行了大规模的量子布局，并正式宣布，当其项目达到一定阶段后将不再向全球开放，这将导致其他国家无法得知最新的研究进展，从而在一定程度上影响我国的战略规划。同时，鉴于量子计算对网络空间安全的威胁，全球各国已达成一致，将重点转向抗量子密码的研究，但各国在这一领域的差距依然存在。在此背景下，我国应继续推进量子计算和抗量子密码领域的研究计划，缩小与西方的差距，切实保障国家的网络信息安全。