抗量子计算_标签

抗量子计算

量子计算的快速发展带给经典密码的巨大冲击使得人们将目光投向了抗量子密码体制的研究。随着量子时代的迫近，抗量子密码体制的研究步伐也在不断加快。引言近三十年，以公钥密码体制为代表的加密方法成为全球化通讯数字基础设备的一个不可或缺的组成部分，在军事、政治、经济、生活等方面都有广泛的应用，在个人、企业和政府的安全通讯中发挥着至关重要的作用。可以说，RSA加密体制、Diffie-Hellman密钥交换、椭圆曲线加密体制、代数同态等等密码体制是近年信息安全领域最受学者青睐的一些加密和签名方案。

这一现状随着量子计算的兴起与快速发展而改变。1994年贝尔实验室的Peter Shor提出了量子质因数分解算法，使得在20世纪80年代之前一直处于纸上谈兵状态的量子计算瞬间成为学者们关注的热点。Shor算法展现了量子计算机可以高效地处理整数分解、离散对数等很多数学难题，这种利用物质和能量的物理性质进行计算的新技术使得一切公钥密码体系的假设不再成立。自Shor算法提出之后，近二十年里量子算法理论有了极大发展。在针对物理模仿、数论和拓扑结构相关的一些研究中，人们又发现了能够完成指数级提速的量子算法，包括在搜索成绩、查找碰撞和布尔公式的评价的相关多类成绩上有更多过度的提速计算的量子算法。特别是，Grover算法在非结构化的搜索上提供了平方的提速计算。虽然这种提速计算不会使得加密技术彻底无效，但为了保持原有的安全性水平，密码方案中就必须增大密钥的规模。因此，一个足够强大的量子计算机将使许多之前通讯方式处于风险之中，包括从加密过程的密钥交换阶段到数字认证阶段。

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

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

量子计算对于传统密码的理论威胁、量子计算机相关技术的高速发展、各国政府量子战略和政策的启动和推进，无不让密码学专家学者感受到一种前所未有的紧迫感。如果真如一些专家预测20年内将出现实用大型量子计算机，抗量子计算密码的研究将刻不容缓。抗量子计算密码由于对抗量子计算密码的迫切需求，2006年，国际上致力于抗量子计算密码研究的学者在比利时召开了第一届国际抗量子密码学会议(PQCrypto 2006)，在这次会议上，各国学者提出了多种抗量子计算密码体制，其中以多变量公钥密码体制类居多，也提出了基于格的密码体制、基于纠错码的体制和基于Hash函数的签名方案。此后，在历届国际抗量子密码会议上都会有所改进、拓展和创新，初步形成了以多变量公钥密码体制、基于Hash函数的数字签名方案、基于编码的密码体制和基于格的密码为主的四大类抗量子密码体制。

一个多变量公钥密码系统由有限域上一组二次多项式作为它的公钥映射。它的主要安全假设为求解有限域上非线性方程组是NP困难问题。最早的多变量公钥密码体制是Tsuii和Imai提出的，20世纪80年代起他们就已经开始这个领域的研究。早期的多变量公钥密码体制研究成果主要在日本，1988年，Matsumoto和Imai提出了第一个现代化形式的多变量公钥密码形式。随后的20多年里，多变量公钥密码体制受到了专家们的广泛关注。美国辛辛那提大学的Jintai Ding、日本的Kohtaro Tadaki、台湾的Bo-Yin Yang等很多知名学者在多变量公钥密码领域展开研究，并在历届抗量子密码会议上发表了多篇文章。此外，我国学者管海明引入单向函数链的概念，提出了有理分式公钥密码系统；张焕国、王后珍等引入了Hash函数的认证机制构造了扩展多变量公钥密码算法。基于抗量子计算的优势，未来多变量公钥密码的研究将进入一个新的高度。

基于Hash函数的数字签名主要指Merkle签名方案。1978年Rabin首次提出了一次签名方案，验证签名时需要与签名者进行交互。次年，Lamport提出了一个更有效的一次签名方案，该方案并不需要与签名者进行交互；Diffie对Lamport的方案进行了推广来提高其效率，因此，该方案成称为Lamport-Diffie一次签名方案。Ralph Merkle从一次性签名方案开始，借鉴了Lamport和Diffie的工作，发明了Merkle数字签名方案。

Merkle的思想是用Hash树将多个一次性验证密钥(Hash树的叶子)的有效性降低到一个公钥(Hash树的根)的有效性。他最初的构造与RSA等方案相比并不够有效，然而由于Merkle签名方案的安全性是基于Hash函数的抗强碰撞性，并且理论计算表明最先进的Hash函数能确保Merkle签名方案的高安全性级别，抵御量子计算的攻击，因此，Merkle签名方案仍然受到了学者们的青睐。Michael Szydlo、Johannes Buchmann、Erik Dahmen、Michael Schneider等一大批学者对Merkle的方案进行了改进。目前，基于Hash函数的签名是代替RSA和椭圆曲线最有前途的签名方案。

基于编码的密码体制算法核心是应用了一种纠错码C，主要特征是编码时添加一定数量的错误码字或根据码C的检验矩阵计算伴随式。基于纠错码的第一个密码体制是1978年McEliece提出的公钥加密方案。该方案安全性高且加密运算快，但为了安全它的公钥规模和签名代价太大。1986年Niederreiter提出了背包型基于编码的公钥密码体制。Niederreiter的密码体制是基于GRS码而不是McEliece体制使用的Goppa码。1994年李元兴、王新梅等人证明了这两种公钥方案在安全性上是等价的。由于这两种加密方案都不能用于数字签名，1990年王新梅提出了第一个基于编码的数字签名方案——Xinmei方案。1991年李元兴构造了一类同时具有签名、加密和纠错能力的公钥体制。随后，人们对McEliece体制进行了一系列的改进，最重要的是2001年由Kobara和Imai提出的改进方案。在抗量子计算密码被推上研究前沿之后，Bhaskar Biswas、Nicolas Sendrier、Stefan Heyse、Daniel J. Bernstein等诸多专家学者在抗量子会议上展示了他们对McEliece体制的改进方案。由于基于数论的公钥密码体制容易受到量子计算的攻击，基于编码的公钥密码体制已然成为基于数论的公钥密码体制的一个很好的替代。

基于格的密码体制基础是格上面的一些困难问题，如最短向量问题(SVP)、最近向量问题(CVP)、最小基问题(SBP)等。在量子计算飞速发展的时代背景下，学者们对格密码对抗量子计算寄予厚望。自1996年Ajtai首次在格难题基础上提出一个具有里程碑意义的密码体制后，格理论的相关研究不断取得突破，已经逐步成为抵抗量子计算攻击的公钥密码体制理论的核心研究内容。基于格的公钥密码算法以其安全性高和效率高的优势受到研究者的持续关注。1996年Hoffstein、Pipher和Silverman提出了NTRU (Number Theory Research Unit)公钥密码体制，该体制具有抗量子攻击、安全性强、运行速度快、密钥生成快、所需内存小等优势。由于基于NTRU体制的数字签名方案并不理想，2000年，Hoffstein等人利用NTRU提出了NSS签名体制，随后在2001年和2003年对签名方案进行了改进。在2006年抗量子会议召开之后，几乎每届抗量子会议都会提出新的或改进的格密码方案。抗量子密码的最新进展由于对抗量子计算密码的迫切需求，2006年，国际上致力于抗量子计算密码研究的学者在比利时召开了第一届国际抗量子密码学会议(PQCrypto 2006)，在这次会议上，各国学者提出了多种抗量子计算密码体制，其中以多变量公钥密码体制类居多，也提出了基于格的密码体制、基于纠错码的体制和基于Hash函数的签名方案。此后，在历届国际抗量子密码会议上都会有所改进、拓展和创新，初步形成了以多变量公钥密码体制、基于Hash函数的数字签名方案、基于编码的密码体制和基于格的密码为主的四大类抗量子密码体制。

2006年至今，国际抗量子密码会议分别在比利时、美国、德国、中国台湾、法国、加拿大、日本和荷兰陆续召开，这也直接导致了近十年来抗量子密码体制的飞跃式发展。从这八届国际抗量子密码年会可以看出，无论抗量子密码种类的增加，还是同一类抗量子密码的不断改进、优化、拓展直至成熟，都充分展示了抗量子密码的时代性和生命力。