后量子密码算法的研究内容与展望

　　摘要：密码是网络通信与信息安全的重要技术堡垒,随着量子算法研究的不断进步,经典密码体制在信息安全保障上面临着巨大威胁。目前,后量子公钥密码算法是理论证明能够抵御量子计算机攻击的核心力量。笔者通过量子算法对现代密码安全形成的威胁进行全面的介绍和总结,对当前后量子密码的发展以及国内外最新研究进展进行探讨与评价,针对该领域中取得许多突破性研究成果的四类主要的后量子密码算法进行分析,表明后量子密码的研究在信息安全中的重要性,并指出未来可能的研究方向。

　　关键词：信息安全; 后量子密码; 公钥密码体制; 保密通信;

　　The Application and Analysis of Post Quantum Cryptography in Information Security

　　Yang Yanling

　　Hanshan Normal University

　　Abstract：Cryptography is an important technical bastion of network communication and information security.With the progress of quantum algorithm research,classical cryptography is facing a huge threat in information security.Nowadays the post quantum public key cryptosystem is the core that can resist the attack of quantum computer.In this paper,the threat of quantum algorithms to modern cryptography is introduced and summarized comprehensively,the development of post quantum cryptography and the internationally latest research progress are discussed and evaluated analyze four kinds of main post quantum cryptography algorithms that have made many breakthrough research results in this field,which shows that the research of post quantum cryptography is important in information securityand point out the possible research direction in the future.

　　0 引言

　　近年来,在以知识经济为主导的信息化社会里,网络以及信息系统的安全问题显得尤为突出。量子计算对信息科学的影响,带动了量子计算机、量子通信和量子密码的研究热潮。量子计算机的问世指日可待,有望成为未来计算机发展的主流,同时也对现有的信息安全技术带来巨大挑战。现代计算机以及信息系统的安全依赖以数论问题的难解性为基础的传统密码技术,然而,面对强大的量子分析时,这类密码技术都将变得“不堪一击”。鉴于量子分析技术日趋进步,为有效应对随之而来的量子信息时代,以及量子计算对传统公钥密码技术形成的威胁,研究设计出能够抵御量子计算攻击的新一代后量子密码方案任重道远。

　　1 量子算法的研究意义

　　密码技术是信息安全的核心,关系国家利益和国家网络空间安全层面,对一国的国防系统、军政和民用网络所造成的破坏程度无法估量。如今放眼全球,从各国政府对量子研究的投入力度以及不断推陈出新的研究成果中不难看出,该领域不仅拥有广阔的技术发展前景,还具有重要的国防战略意义。我国在量子信息研究领域也做出了突出贡献,2017年5月,潘建伟的团队已自主研发了10比特超导量子线路样品,成功实现了目前世界上最大数目超导量子比特的纠缠和完整的测量。近期,Google团队在一台53比特的量子计算机上仅用3分20秒便完成了在超级计算机上需要一万年的计算[1],这显示了量子计算超强的运算速度以及优越性,是该领域的又一次巨大突破,将量子计算机的处理能力推向新的高峰。美国政府曾明确表示,该国量子计算研究进行到一定的阶段,将不再对外公布任何相关的技术资料,研究结果将严格保密,也不在学术会议中公开发表关于量子计算研究的进展。可见,量子算法的研究在信息安全中的地位不仅是一个技术层面上的问题,还会影响一个国家的国防、经济和社会稳定的全局战略。

　　2 量子计算能力对现代密码技术的潜在冲击

　　量子计算对现代密码安全的威胁绝不是危言耸听。自2001年,IBM公司研制出7个量子位的量子计算机,就已宣告了量子计算机在应用上的可行性。目前,关于量子算法的极限仍无法确定,对量子计算机的研究仍处于探索阶段,因此,它的普及应用尚有待时日。尽管量子算法对传统密码的威胁需要在量子计算机投入使用后才能真正实现,但是随着研究不断深入,通用型量子计算机的出现指日可待,在可以预期的十几年内,经典公钥密码算法的安全性将受到严峻考验。当前国际上对量子计算机技术的研究与投入,正加速这种潜在威胁成为现实。

　　量子计算机拥有超强计算能力的重要前提是量子算法高效的计算并行性,它可以将原来在经典计算机环境下无法高效解决的一类数学困难问题变得容易计算,缩短求解时间。量子密码的安全主要是建立在量子理论的Heisenberg测不准原理和未知量子态的不可克隆、不可删除定理、测量量子态不可逆塌缩等一系列物理原理的基础上,与攻击者的计算能力无关,是一种基于非数学原理的密码。正是由于量子信息工程的出现,现代密码学的研究从原来的基于数学的密码向基于非数学的密码转变。

　　量子算法中以1994年的Shor's algorithm以及1996年的Grover's algorithm为代表,这两大着名的量子算法在理论上已经被证明对高效求解大多数公钥密码依赖的数学难题,破译对称密码和哈希函数有一定的作用。Shor算法[2]的核心内容是基于傅里叶变换原理,模幂运算的量子求阶算法,可以在多项式内高效解决大整数质因子分解、椭圆曲线离散对数等数学问题,这直接影响到RSA、ElGamal[3]和ECC[4]等公钥密码算法的安全。一旦量子计算机投入使用,以上一系列基于数论难题的传统公钥密码算法的安全性将变得“不堪一击”。Grover量子搜索算法[5]能够提高搜索密钥空间的效率,在速度上达到“指数减半”的效果,提高攻击者成功破解密钥的概率,这对哈希函数和对称密码算法造成极大威胁。但因为该算法在应用上有许多限制条件,所以影响比较有限,防御对策只需要简单地通过适当增加密钥长度,比如至少扩大2倍密钥长度,便可在一定程度上抵抗Grover量子计算攻击。因此,从破解经典密码算法的能力来看,Shor算法比Grover算法发挥的作用更大。

　　实际上,传统公钥密码体制的安全是建立在现代计算机有限的计算能力前提下,即在多项式时间内计算机无法高效求解的数学难题,对于此类难题如果运用量子计算机进行求解却是轻而易举的。但量子计算分析并不能有效求解所有的数学难题,如今仍然存在一些计算复杂性困难问题尚未被量子计算高效破解,这成为研究后量子密码技术的突破口。不可否认未来依然需要依赖密码技术来保障信息安全,为应对量子计算对网络信息安全造成的威胁,在已知的量子算法特征的基础上,研究出能有效抵御量子计算攻击的新一代密码体制是目前最为可行的方案之一。

　　3 后量子密码算法

　　人们对量子计算机实用化的信心以及量子信息时代通信安全的关注,推动着后量子密码研究的不断发展。后量子密码已逐渐成为科研界的热点话题,研究学者们为即将到来的“后量子时代”做准备,力图设计出足以抵御量子计算机攻击的有效密码方案,并将这类研究统称为“后量子密码学”。密码学界把这一类能够有效抵抗经典计算机攻击,又能抵御已知的量子计算攻击的密码算法,称为后量子密码(Post-Quantum Cryptography,简称PQC),或称为抗量子密码(Quantum-resistant Cryptography)[6]。总的来说,后量子密码主要是针对量子计算的特点,结合传统密码的优势设计能够抵御量子计算攻击的密码方案,实现“后量子密码”在应用上的安全性、可靠性和可操作性[7],实现通信数据安全。

　　后量子密码的研究前景广阔,近年来美国和欧洲各国都在大力推动后量子密码的应用和密码算法标准化工作,积极开展后量子密码体制的研究。早在2015年1月,欧盟启动后量子密码算法SAFECRYPTO应用项目,同年3月,整合欧洲多所高校和科技企业力量,开展全球后量子密码算法旗舰项目PQCRYPTO[8],并将其纳入欧盟地平线2020计划。2018年也相继开展了后续的PROMETHEUS项目,致力于打造新一代安全实用的后量子密码方案。

　　作为信息安全有效防御计划的最新一步,2016年4月,美国国家标准与技术研究局NIST发布了“后量子密码学”的研究报告[9],同时为甄选出一套最强的候选算法,美国启动了“抗量子密码算法标准化”工作计划[10],面向全球征集后量子密码标准,意图打造出能够保障网络通信与信息系统免受未来量子计算机攻击的后量子密码算法,预计在2022-2023年完成后量子密码标准算法的起草与发布。截至2017年11月30日,NIST共收到来自全球的候选算法82份。经过NIST的数学家和计算机科学家第一轮评估后,选出26个“后量子密码学标准化项目”的最强候选算法进入第二轮评估,其中,候选公钥加密和密钥建立算法标准有17个,候选数字签名算法标准有9个[11]。此次美国NIST发起的算法征集中,欧洲是参与征集算法的最大来源,在入选的26个候选算法方案中,15个来自欧洲。

　　我国后量子密码算法标准化工作也计划于2022年开展。目前,我国后量子密码技术的研究着眼于国际水平,向国际先进技术迈进,充分调动国内各界研究力量,推动自主研发,致力于保障未来量子计算环境下我国网络空间的安全。从世界各国政府对该领域的投入与支持力度看,研究后量子密码的重要性不言而喻。

　　4 后量子密码的研究内容

　　目前,国际上应对量子计算攻击的研究集中在后量子密码领域,后量子密码学[12]主要研究的是一类量子计算机在多项式时间内无法攻破的密码算法,从而实现量子时代的网络以及信息系统安全。面对强大的量子计算能力,只要从量子算法不擅长求解的一类困难问题入手,实现构造密码算法,便可在一定程度上有效抵御未来量子计算机的攻击。同时,以目前量子计算能力无法高效求解的困难来设计后量子密码系统,既可以提高后量子密码在现代网络中的兼容度,又减少了在实际应用中的阻力。

　　在量子计算环境下,量子计算未能在多项式时间内高效求解的数论难题,例如基于格上的最短/最近向量问题,以及基于编码理论、基于哈希算法和基于多变量的密码体制[13],在后量子密码研究学者们看来,抵御强大的量子计算机攻击,保障信息安全的密码方案主要基于上述几类问题。从国际密码学界的研究热点看,国内外密码学家也着重针对以上这几类密码方案开展大量研究,并取得许多突破性的成果。

　　后量子密码方案以LEE[14]等人提出的理论为最初依据,通过寻找一类经典数学算法,可以在不同平台上抵御量子计算机攻击,具备一定的合理性与实用性。如今,在一系列能够抵抗量子计算的算法方案中,从理论基础或者算法设计的可行度方面看,研究的焦点主要是以下4种类型。

　　4.1 基于编码(纠错码)的密码体制(Code-based cryptography)

　　基于编码的密码体制[15]是以编码理论中的数论难题为基础而设计,这类困难问题包括了随机线性编码解码问题、有界编码解码问题以及列表解码问题等。目前,量子计算的分析能力尚未能攻破此类型算法。基于编码的密码体制已经历了数十年的密码分析,可应用于设计加密、签名方案,其中的典型代表是1978年Robert McEliece提出的基于隐藏Goppa码的“McEliece公钥加密系统”[16],以纠错编码(error correcting codes)理论为安全核心,被认为是一种可靠的密码系统。该加密系统将二元不可约的Goppa码[17,18]作为专有密钥,具有快速多项式时间译码算法的特点,将待传递的明文信息视为一个合法码字,加密过程中为明文码字添加一个随机码,解密过程相当于对密文进行译码,只有掌握有效译码算法的合法接收者才能将密文恢复成明文信息。但是使用Goppa码作为专有密钥,考虑到其密钥尺寸太大而造成效率低下的问题,人们曾经试图使用其他纠错码来替代Goppa码,但都被攻破。至今,基于Goppa码的McEliece公钥密码算法被认为是在后量子密码系统中最安全的应用之一,能够保障量子时代的信息安全。

　　4.2 基于Hash算法的密码体制(Hash-based cryptography)

　　由于现有大部分传统公钥密码的安全性是建立在图灵机模型下无法求解的经典困难问题的基础上,例如,计算有限域、椭圆曲线群上的离散对数问题等,区别于传统公钥密码体制,基于Hash算法的密码体制的安全核心是运用了Hash算法的抗碰撞性[19],由传统的Hash函数,以及任意的一次性签名算法构造并实现数字签名,能够保障信息安全以及不可否认性。基于Hash密码体制的典型代表算法是Merkle在1979年提出的Merkle-hash树签名方案[20],该方案虽然能够抵御量子计算攻击,但并不具备多密钥交换的功能,因此,在信息安全实用性方面会有所限制。

　　4.3 基于格的密码体制(Lattice-based cryptography)

　　多数传统密码系统安全都建立在一个平均情况下问题的难解性,例如RSA算法,就是通过某种特殊方式将问题转化成平均情况下的求解困难。实际上,基于最坏情况难解性的密码系统会更安全,最坏情况难解性是计算复杂性理论中的概念,指的是问题只有在某些输入下才是难解的,而在其他情况下求解却是容易的[21]。第一个基于格的密码方案是由Ajtai和Dwork在1997年提出的Ajtai-Dwork密码体制[22],将格问题的平均情况难解性(Average-case)与最坏情况难解性(Worst-case)联系起来抵抗量子计算攻击。格理论研究的是在大维数的格上基于最短向量问题(SVP)和最近向量问题(CVP)等NP难问题,用于设计加密、签名、伪随机发生器、密钥交换协议、基于身份的加密以及全同态密码等抵御量子计算攻击的安全防御机制,可见,基于格的公钥密码方案具有较好的发展潜力与可扩展性。格理论作为一种设计密码算法方案,在研究过程中不断有突破性进展,密钥尺寸在不断改善,运算速度也在不断提高。基于格的密码体制中,最着名的加密方案是1998年提出的NTRU公钥加密体制[23],是迄今为止最实用的算法,有望替代现阶段使用最多的RSA公钥密码方案,成为最具吸引力的后量子密码算法之一。

　　4.4 基于多变量密码体制

　　在后量子密码领域里,多变量公钥密码体制(Multivariate Public Key Cryptosystem,简称MPKC)[24]正逐步显示它的重要地位,如今对多变量公钥密码体制的设计与安全性分析已成为密码学研究的热点之一。基于多变量密码体制的核心是求解有限域上随机产生的多变量非线性多项式方程组的困难问题,其运算只需要在较小的有限域上完成,所以基于多变量密码的效率较高。存在的缺陷是由于二次多项式多变量公钥密码的安全等级不高,因此需要构造更高次的多变量公钥密码体制[25],随着变量个数与多项式次数的增多,造成密钥尺寸增大,这难免也会影响安全效率。考虑到公钥量以及安全问题,目前大部分多变量公钥密码方案是基于多元二次多项式方程组的求解困难来构造,尚不具有可证明安全性。至今量子算法中的shor算法和Grover算法都无法对这类方程进行有效攻击,因此,MPKC被认为能够有效抵抗量子计算攻击的密码体制。

　　5 研究展望

　　随着量子信息时代的到来,量子计算机的应用带来的安全威胁,从理论分析上看,并不是所有的经典密码算法都会被淘汰,正如麻省理工科技评论认为,量子计算机与经典计算机并不是对立的,量子计算机在解决某些问题上并不比经典计算机强,两者之间应该是共生关系,在未来进一步发展中相互渗透、协作解决问题,共同保障信息传输安全。

　　在量子计算领域中,密码安全体系的基础尚未稳固,如何保障量子计算机下的数据和信息安全,是国际密码学界持续关注的焦点。同时,后量子密码是抵御量子计算攻击的核心技术,对后量子密码体制安全模型的分析及设计的投入力度至关重要。从技术的需求和应用的广泛程度出发,利用公钥密码的优势,在传统公钥密码的成果基础上,将其升级到后量子公钥加密,有助于完善密钥交换和签名算法,这标志着信息安全向量子保密通信技术领域迈出了关键的一步,即将成为新时代密码体制的技术基础。

　　量子计算机的发展从客观上看,是对密码技术提出了更高要求,从主观上讲,则要求加强对抗量子算法分析的密码安全基础研究。笔者相信,后量子密码学将会把人们带入一个全新的密码技术时代。着名密码学家Bernstein认为,从时代发展和应用前景的角度看,后量子密码的出现具有“里程碑”式意义,因此,应当加紧对后量子密码方案的研究及改进,当量子信息时代到来以及量子计算机通用时,人们仍然能保障网络空间及信息系统的安全。

　　6 结 语

　　近年来,后量子公钥密码方案的研究取得了丰硕的成果,后量子公钥密码的国际标准化制定工作也在进行中,现在所有的后量子密码安全性验证都只是基于理论分析,与传统的密码技术面临的缺陷一样,理论上可论证的安全性和在实际应用中的安全性并不能完全等同,在实际使用过程中,计算机的硬件和系统的非理想性也可能成为被攻击者利用的漏洞。

　　尽管如此,仍可预见量子信息时代下,多数传统公钥密码算法的安全保障能力将会面临巨大的挑战。现代密码学领域在慢慢发展,量子计算时代的到来并不是现代密码的终结,后量子密码也不可能完全取代传统密码,两者之间相辅相成、互相补充,能够更好地保护网络信息传输以及系统安全。

　　参考文献

　　[1]FIINANCIAL TIMES.Google Claims to Have Reached Quantum Supremacy[EB/OL].(2019-09-20)[2020-04-15].http://nmg.naihes.cn/rwt/CNKI/https/P75YPLUGPRYGG55N/content/b9bb4e54-dbc1-11e9-8f9b-77216ebe1f17.

　　[2]Shor P W.Algorithms for Quantum Computation:Discrete Logarithms and Factoring[C]//In 35th Annual Symposium on Foundations of Computer Science,1994:124-134.

　　[3]Gamal T E.A Public Key Cryptosystem and A Signature Scheme Based on Discrete Logarithms[J].IEEE Transactions on Information Theory,1984,31(4):469-472.

　　[4]Koblitz N.A Course in Number Theory and Cryptography[J].Geometric & Functional Analysis,2016,25(1):1-86.

　　[5]Grover L K.A Fast Quantum Mechanical Algorithm for Database Search[C]//Proceedings of the Twenty-eight Annual ACM Symposium on Theory of Computing,1996:212-219.

　　[6]Whitfield D,Martin E H.New Directions in Cryptography[J].IEEE Transactions on Information Theory,1976,22(6):644-654.

　　[7]潘峰.后量子密码体制在信息安全等级保护中的运用分析[J].信息与电脑,2017,18(7):211-212.

　　[8] Hoffstein J,Pipher J,Silverman J H.NTRU:A ring-based public key cryptosystem[C]//International Algorithmic Number Theory Symposium,1998:267.

　　[9]Chen L,Jordan S,Liu Y,et al.Report on post-quantum cryptography[EB/OL].(2016-04-28)[2020-04-15].http://dx.doi.org/10.6028/NIST.IR.8105.

　　[10]Andreas Hülsing,Lea Rausch,Johannes Buchmann.Optimal Parameters for XMSSMT[J].Security Engineering and Intelligence Informatics,2017,37(2):187-189.

　　[11]NIST.Post quantum crypto project[EB/OL].(2016-06-28)[2020-04-15].http://nmg.naihes.cn/rwt/CNKI/https/MN3YEZ3PN3VYG7BPM7YYG/Projects/Post-Quantum-for-Cryptography/Post-Quantum-Cryptography-Standardization/call-for-Proposalls.List of First Round candidates available.

　　[12]Bernstein Daniel J.Buchmann,Johannes A.Post-quantum Cryptography[M].Heidelberg:Springer,2009.

　　[13]Craig G.Fully Homomorphic Encryption Using Ideal Lattices[C]//In Michael Mitzenmacher,2009(24):169-178.

　　[14]LEE E,LEE S J,HAHN S G.Pseudorandomness from Braid Groups[C]//Springer.21st Annual International Cryptology Conference on Advances in Cryptology,2001:486-502.

　　[15] McEliece,Robert J.A Public-key Cryptosystem Based on Algebraic Coding Theory[J].Technical report,1978(15):114-116.

　　[16]Mceliece R.A Public-Key Cryptosystem Based on Algebraic Coding Theory[J].Dsn Progress Report,1978(56):42-44.

　　[17]MacWilliams,F.J,Sloane,N.J.A.The theory of error-correcting codes.Parts I,II.[M].Netherlands:North-Holland,1977.

　　[18]McEliece R.The Theory of Information and Coding[M].Cambridge:Cambridge University Press,2002.

　　[19]刘文瑞.抗量子计算攻击密码体制发展分析[J].通信技术,2017,50(5):1054-1059.

　　[20]Ralph M.Protocols for Public Key Cryptosystems[J].IEEE Symposium on Security and Privacy,1980(9):122-134.

　　[21]王兆丽,杨明,韩敬利.基于格的公钥密码方案[J].军事通信技术,2014(35):79-86.

　　[22]Ajtai M,Dwork C.A Public-key Cryptosystem with Worst-case/average-case Equivalence[C]//In Proceedings of the 29th Annual ACM Symposium on Theory of Computing(STOC),1997:284-293.

　　[23]Hoffstein J,Pipher J,Silverman J H.NTRU:A Ring Based Public Key Cryptosystem[C]//In Proceedings of ANTS-III,1998:267-288.

　　[24]Ding J,Schmidt D.Rainbow,a new multivariable polynomial signature scheme[C]//Applied Cryptography and Network Security—ACNS,2005:164-175.

　　[25]鲁刚.多变量公钥密码体制的设计与安全性研究[D].成都:电子科技大学,2017.