抗量子密码体制发展研究

量子计算的快速发展带给经典密码的巨大冲击使得人们将目光投向了抗量子密码体制的研究。随着量子时代的迫近，抗量子密码体制的研究步伐也在不断加快。本文回顾了以多变量公钥密码体制、基于Hash

近三十年，以公钥密码体制为代表的加密方法成为全球化通讯数字基础设备的一个不可或缺的组成部分，在军事、政治、经济、生活等方面都有广泛的应用，在个人、企业和政府的安全通讯中发挥着至关重要的作用。可以说，RSA 加密体制、Diffie-Hellman 密钥交换、椭圆曲线加密体制、代数同态等等密码体制是近年信息安全领域最受学者青睐的一些加密和签名方案。

这一现状随着量子计算的兴起与快速发展而改变。

1994 年贝尔实验室的Peter Shor 提出了量子质因数分解算法[1]，使得在20 世纪80 年代之前一直处于纸上谈兵状态的量子计算瞬间成为学者们关注的热点。Shor 算法展现了量子计算机可以高效地处理整数分解、离散对数等很多数学难题，这种利用物质和能量的物理性质进行计算的新技术使得一切公钥密码体系的假设不再成立。自Shor 算法提出之后，近二十年里量子算法理论有了极大发展。在针对物理模仿、数论和拓扑结构相关的一些研究中，人们又发现了能够完成指数级提速的量子算法，包括在搜索成绩、查找碰撞和布尔公式的评价的相关多类成绩上有更多过度的提速计算的量子算法[2]。

特别是， Grover算法在非结构化的搜索上提供了平方的提速计算。虽然这种提速计算不会使得加密技术彻底无效，但为了保持原有的安全性水平，密码方案中就必须增大密钥的规模。因此，一个足够强大的量子计算机将使许多之前通讯方式处于风险之中，包括从加密过程的密钥交换阶段到数字认证阶段。

量子计算对于传统加密体制的威胁绝不仅仅是耸人听闻，庸人自扰。迄今为止，量子算法已经能够破译包括RSA 公钥加密体制、Diffie-Hellman 密钥交换、椭圆曲线加密体制、Buchmann-Williams 密钥交换、代数同态在内的多类密码[3]。而且，随着近些年计算机技术和新型材料技术的飞速发展，量子计算机的研究正以不可阻挡的势头占领信息通讯和网络安全的高地。科学技术的发展尤其是量子科技的日新月异，使得学术界越来越相信，量子计算机的出现和实用化将只是时间问题。

此外，由于量子计算机对传统加密体制具有重大的威胁，许多国家政府已经认识到量子计算机的战略意义。美国政府在此领域率先行动，投入巨资启动了五个量子计算机研究计划：美国国防高级研究计划局的“量子信息科学与技术发展规划”、美国国家安全局的ARDA5 计划、美国科学基金会的QuBIC计划、美国宇航局的QCTG 计划和美国国家标准与技术研究院的PLQI 计划。此后，日本、欧盟、加拿大等国家和地区也相继启动了量子计算机发展规划。我国也由中国科技大学潘建伟团队投入量子计算机的研发当中，在国际上首次利用光量子计算机实现了Shor 量子分解算法，并且在2016 年发射了国际上第一颗量子卫星。

量子计算对于传统密码的理论威胁、量子计算机相关技术的高速发展、各国政府量子战略和政策的