抵抗量子计算攻击的后量子密码，市场规模近百亿美元

出品  光子盒研究院

1976年，斯坦福大学的Whitfield Diffie和Martin Hellman两人共同发表了论文《密码编码学新方向》，指出在通信双方之间不直接传输加密密钥的保密通信是可能的，并首次提出了非对称公钥密码体制的思想，把密钥分为加密的公钥和解密的私钥，引发了密码学史的一场革命。而之前的对称加密技术，信息的发出方和接收方共享同样的密钥。

他们在理论基础上提出了一个密钥交换协议，叫作Diffie-Hellman算法，这是世界上第一个公开密钥算法。它的有效性依赖于离散对数的难度。

此后，公钥密码体制不断完善。1977年，Ron Rivest、Adi Shamir和Leonard Adleman三人提出了RSA算法。它基于一个简单的数论事实：将两个质数相乘较为容易，反过来，将其乘积进行因式分解而找到构成它的质数却非常困难。

到了1985年，一种新的公钥算法由Neal Koblitz和Victor Miller分别独立提出，即椭圆曲线加密算法（ECC），它是基于椭圆曲线数学理论实现的。相比RSA，ECC优势是可以使用更短的密钥，来实现与RSA相当或更高的安全。

近三十年来，公钥密码体制有效解决了对称密码面临的安全密钥交换问题，因而广泛应用于公钥基础设施、数字签名、联合授权、公共信道密钥交换、安全电子邮件、虚拟专用网以及安全套接层等大量网络通信活动之中。

许多至关重要的通信协议主要依靠三大核心密码模块：公钥加密、数字签名和密钥交换。而这些模块主要是利用Diffie-Hellman、RSA和ECC来实现的。

以上三大算法建立在复杂的数学计算基础上，包括：离散对数 (及椭圆曲线版本)、大整数分解等，以至于经典计算机要花费太长的时间，并使用过多的计算能力来解决问题。

然而，密码学家们低估了算力提升的潜力，比如，RSA-768，曾被认为需要“7000年”才能破解，但在十几年前，几位研究人员用非常普通的超算，仅用半天的时间就破解了它。

随着Shor算法的提出，包括Diffie-Hellman、RSA和ECC等非对称密码算法已经从理论上被证明彻底丧失了安全性。因为公钥密码算法安全性依赖的数学问题可以被高效的量子算法所解决。

成熟的量子计算机仍然需要数年乃至数十年时间才会出现。一些专家预测，未来20年可以建立足够大型的量子计算机，以从根本上破解所有目前在用的公钥密码方案。

但是要知道，部署现代公钥加密基础设施也花了近20年的时间，因此，部署能够抵抗量子计算攻击的后量子密码已经迫在眉睫。

我们为什么需要后量子密码？

实际上，传统公钥密码体制的安全是建立在经典计算机有限的计算能力前提下，即在多项式时间内计算机无法高效求解的数学难题，对于此类难题，如果运用量子计算机进行求解却是轻而易举的。

特别是1994年提出的Shor算法，其核心内容是基于傅里叶变换原理，模幂运算的量子求阶算法，可以在多项式时间内高效解决大整数质因子分解、椭圆曲线离散对数等数学问题。这直接影响到D-H、RSA和ECC等公钥密码算法的安全。

例如，一个每秒能做1012次运算的机器，破解一个300位RSA密码需要15万年。据美国国家科学、工程和医学院2018年发表的量子计算报告预测，运行Shor算法的量子计算机将能够在一天内破解1024位RSA密码。破解300位密码，不过是一眨眼的时间。

Shor算法与经典算法的比较

但量子计算分析并不能有效求解所有的数学难题，仍有一些计算复杂性问题尚未找到高效的量子计算攻击方法，这是研究新密码技术的突破口，而基于这些问题设计的密码叫作后量子密码（Post-quantum cryptography，PQC），也叫抗量子密码（Quantum-resistant cryptography）。

所谓“后”，是因为量子计算机的出现，现有的绝大多数公钥密码算法能被足够大和稳定的量子计算机攻破，那么，能够抵抗这种攻击的密码算法可以在量子计算机和其之后时代存活下来，因此被称为“后”量子密码。

近十几年来，后量子密码成为密码学的热点研究问题。密码学家认为，面对强大的量子计算能力，只要从量子算法不擅长求解的一类困难问题入手，实现构造密码算法，就可以在一定程度上有效抵抗未来量子计算机的攻击。

在一系列能够抵抗量子计算的算法方案中，从理论基础或者算法设计的可行性来看，后量子密码主要包括以下4种类型。

基于格 (Lattice-based)

基于编码 (Code-based)

基于多变量 (Multivariate-based)

基于哈希 (Hash-based)

基于格的密码体制

基于格的密码体制是指在大维数的格上，基于最短向量问题（SVP）和最近向量问题（CVP）等数学难题而构造的密码体制。

SVP是指在大维数格中寻找长度最短的非零向量，CVP是指在大维数格中寻找和固定向量距离最短的向量，这两个问题都是NP-Complete问题，即多项式复杂程度的非确定性问题。

格理论最初是作为一种密码分析工具被引入到密码学中的，应用于分析背包密码体制、RSA密码体制等。1997年，Ajtai和Dwork提出了第一个基于格的密码体制Ajtai-Dwork，随后在1998年Hoffstein、Pipher和Silverman提出了NTRU密码体制。但当时基于整数分解及离散对数的公钥密码体制是主流，格密码一直没有得到足够的重视。

直到2009年，IBM的研究员C. Gentry基于格密码构造了首个全同态密码方案，格密码才得到了广泛的发展。

与基于数论问题的密码算法构造相比，基于格的算法可以实现明显提升的计算速度、更高的安全强度。可以实现加密、数字签名、密钥交换、属性加密、函数加密、全同态加密等各类现有的密码学构造。

与其他几种实现后量子密码的方式相比，格密码的公私钥尺寸更小，并且安全性和计算速度等指标更优。基于格的算法的安全性依赖于求解格中问题的困难性。在达到相同（甚至更高）的安全强度时，基于格的算法的公私钥尺寸比上述三种构造更小，计算速度也更快。

基于编码的密码体制

基于编码的密码体制是以编码理论中的数论难题为基础而设计的，这类困难问题包括了随机线性编码解码问题、有界编码解码问题以及列表解码问题等。目前，量子计算的分析能力尚未能攻破此类型算法。

基于编码的密码体制已经历了数十年的密码分析，可应用于设计加密、签名方案，其中最具代表的是1978年Robert McEliece提出的基于隐藏Goppa码的McEliece公钥加密系统，以纠错编码（error correcting codes）理论为安全核心，被认为是一种可靠的密码系统。

但使用Goppa码作为专有密钥，考虑到其密钥尺寸太大而造成效率低下的问题，人们曾经试图使用其他纠错码来替代Goppa码，但都被攻破。至今，基于Goppa码的McEliece公钥密码算法被认为是在后量子密码系统中最安全的应用之一，能够保障量子时代的信息安全。

基于多变量的密码体制

多变量公钥密码体制（MPKC）核心是求解有限域上随机产生的多变量非线性多项式方程组的困难问题，其运算只需要在较小的有限域上完成，所以基于多变量密码的效率较高。

至今量子算法中的Shor算法和Grover算法都无法对这类方程进行有效攻击，因此，MPKC 被认为能够有效抵抗量子计算攻击的密码体制。

但它也存在缺陷，由于二次多项式多变量公钥密码的安全等级不高，因此需要构造更高次的多变量公钥密码体制，随着变量个数与多项式次数的增多，造成密钥尺寸增大，这难免也会影响安全效率。

考虑到公钥量以及安全问题，目前大部分多变量公钥密码方案是基于多元二次多项式方程组的求解困难来构造，尚不具有可证明安全性。

基于Hash的密码体制

区别于传统公钥密码体制，基于Hash的密码体制核心是运用了Hash算法的抗碰撞性，由传统的Hash函数，以及任意的一次性签名算法构造并实现数字签名，能够保障信息安全和不可否认性。

基于Hash密码体制的典型代表算法是Ralph C. Merkle在1979年提出的Merkle-hash树签名方案，该方案虽然能够抵御量子计算攻击，但并不具备多密钥交换的功能，因此在信息安全实用性方面会有所限制。

4种后量子密码方案对比

由于后量子密码学起步较晚，目前尚未实现算法标准化。2016年时，美国国家标准与技术研究局（NIST）才启动了“抗量子密码算法标准化”工作计划，面向全球征集后量子密码标准。

截止2017年11月30日第一轮结束，NIST共收到来自全球的候选算法82份。在进行初步筛选后，NIST 公布了69个“完整且适合”的草案，包括基于格、编码、多变量、哈希以及其他方法构造的后量子密码算法。

其中，基于格和编码的构造是最多的，且主要被用于构造公钥加密（密钥交换）算法；由于基于多变量的陷门构造相对更为可行和高效，因此主要集中于数字签名方案，公钥加密方案较少；而基于哈希的构造方案中树状结构的使用，目前只有数字签名的构造，缺少公钥加密算法。

全球推动后量子密码标准化

密码学家们开始关注量子计算的威胁是在2006年。国际密码逻辑研究联合会举办了第一届后量子密码技术国际会议。此次会议成果集中汇总于2008年出版的《后量子密码》，该书详细介绍了后量子密码研究的几乎全部潜在领域，在此之后，国际后量子密码技术的发展也基本上遵循着该书构建的技术框架。

近年来，美欧日处于后量子密码研究和应用领域的领先地位。

早在2015年1月，欧盟启动后量子密码算法SAFECRYPTO应用项目，在对称加密、对称授权、公钥加密以及公钥签名系统领域都提出了相关标准化建议。

同年3月，整合欧洲多所高校和科技企业力量，开展了全球后量子密码算法旗舰项目PQCRYPTO，并将其纳入欧盟地平线2020计划。2018年又开展了后续的PROMETHEUS项目，致力于打造新一代安全实用的后量子密码方案。

2015年8月，美国国家安全局（NSA）公开宣布由于面临量子计算的威胁，其计划将联邦政府各部门目前使用的ECC/RSA算法体系向后量子算法进行迁移。

而负责标准制定的NIST也在2016年4月发布了“后量子密码学”的研究报告，并在同年启动了“抗量子密码算法标准化”工作计划，面向全球征集后量子密码标准，其中包括公钥密码、数字签名以及密钥交换算法，建议征集的截止日期定于2017年12月。

此后，国家标准与技术局会利用3-5年时间分析这些建议并发布相关分析报告，最终的标准拟制工作也将耗时1-2年。预计在2022-2023年完成后量子密码标准算法的起草与发布。

NIST在《后量子密码学》研究报告中表示，一些专家甚至预测，在未来的20年左右，可以建立足够大型的量子计算机，以从根本上破解所有目前在用的公钥密码方案。部署现代公钥加密基础设施花了近20年的时间，要实现从目前广泛使用的密码系统到抗量子计算的相应体系的平滑和安全迁移需要相当多的努力。

因此，不论我们对量子计算时代到来的时间估计是否精确，我们现在必须开始着手，让我们的信息安全系统能够抵抗量子计算。

量子计算对常见的密码算法的影响

NIST后量子密码团队负责人Dustin Moody曾在AsiaCrypt 2017会议上表示：公钥密码算法需要后量子密码算法代替；对称密码算法并不那么紧迫需要新算法代替，可以通过调整参数解决。

关于对称密码系统面临的量子计算威胁，目前仅有Grover算法对AES等对称密码系统产生影响，而且与经典计算机的破解速度相比，其能够产生效率优势只是一般方法的平方。通过密钥长度加倍的措施，这种威胁可以得到有效化解。

但Shor算法的提出，非对称密码算法已经从理论上被证明彻底丧失了安全性。

截止2017年11月30日，NIST共收到来自全球的候选算法82份。经过NIST的数学家和计算机科学家第一轮评估后，选出26个“后量子密码学标准化项目”的最强候选算法进入第二轮评估，其中，候选公钥加密和密钥建立算法标准有17个，候选数字签名算法标准有9个。

入选第二轮的名单：

https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

这次参加NIST后量子密码标准征集工作的也有来自中国的团队，包括：密码科学技术国家重点实验室的张江、上海交大的郁昱、复旦大学的赵运磊、中科院信工所的路献辉团队。

但最终进入第二轮评估的只有路献辉团队的LAC（公钥加密和密钥建立算法），另外，美国辛辛那提大学的华人教授丁津泰团队的Rainbow（数字签名算法）也进入26强。

可以说，NIST征集后量子密码算法是举全球之力，各国之间更多的是合作，而非对抗。

2019年5月，第十届国际后量子密码会议在重庆召开，这场后量子密码盛会第一次来到了中国。会上，NIST后量子密码团队负责人Moody简单分析了26种入围算法的优缺点，并表示，NIST鼓励更多的业内人士积极参与，踊跃评论，提出更多高质量的提案。

近年来，中国也开始推动后量子密码的标准化。在2018年11月举办的第六届量子安全国际会议上，时任中科院信息工程所副所长荆继武表示，我国在后量子密码算法上还没有真正的原创性成果，基本在做跟踪研究。但他个人认为，我国可在2020年左右做出抗量子密码机和密码模块，在2022年启动抗量子密码的标准化程序。

百亿美元的后量子密码市场

根据Inside Quantum Technology的一份最新报告，到2029年，后量子密码（PQC）软件和芯片的市场将增至95亿美元。PQC功能将嵌入到众多设备和环境中，其中80%以上的收入将来自网络浏览器、物联网、机床和网络安全行业本身。

随着时间的推移，Web浏览器将用PQC加密方案取代当前的RSA、ECC和Diffie-Hellman算法。Google已经对基于浏览器的PQC进行了实验，量子安全浏览器最终将成为未来十年任何金融交易的必备工具。到2029年，基于浏览器的PQC收入将达到18亿美元。

网络安全行业提供的服务越来越可能涉及PQC。例如，业界将为电子邮件和VPN提供PQC即服务（PQC-as-a-service）产品。到2029年，PQC相关网络安全产品的收入将达到16亿美元。

IQT认为，PQC最大的细分市场将出现在制造业。例如，由黑客造成的生产工厂中断可能会导致运营中断或导致产品出现问题。考虑到未来工厂相互关联的本质，似乎需要某种量子安全保证。到2029年，机床行业在PQC产品上的支出将达到29亿美元。

尽管后量子密码标准化工作还在进行中，但许多科技巨头已经跃跃欲试了。比如，2018年微软发布了一个OpenVPN的开源项目分支，名为PQCrypto-VPN，这个项目在OpenVPN中实现了后量子密码（PQC）。可以在VPN中测试PQC算法的功能和性能。

微软在Github上发布了PQCrypto-VPN，它允许任何人使用三种不同的后量子密码协议构建一个OpenVPN实现加密通信。这些协议是：

Frodo：基于错误问题学习的密钥交换协议

SIKE：基于超奇异同源Diffie-Hellman的密钥交换协议

Picnic：使用对称密钥基元和非交互式零知识证明的签名算法

不过，微软警告说，这个项目仍然是实验性的，还需要几年时间才能确定算法能否真正抵御量子计算攻击。因此，它暂时不能用于保护敏感数据。

另一家科技公司华为，也计划尽早为密钥协议引入安全的后量子算法，以确保其产品的长期安全性。华为正在关注后量子算法的各种标准化活动，并计划在标准化工作结束之前将一些候选算法试验性地引入他们的产品中，以应对对密钥协商过程的囤积攻击。

关于PQC和QKD的区别

相比于后量子密码，公众似乎更了解量子密钥分发（QKD）。从功能来看，二者都能用于加密，但从原理来看，二者完全不同。QKD（BB84协议）基于量子力学原理，它利用的是量子不可克隆、海森堡不确定性原理、量子纠缠等特性。PQC则完全基于数学原理。

从对量子密码技术的投入来看，基于物理原理的QKD与基于数学原理的PQC有着一定的竞争关系。虽然前者已经推出了商业化的产品，而后者还没进入实际应用阶段，但相信随着NIST后量子密码标准的遴选进程，后量子密码技术将会得到更多的关注和投入。

实际上，QKD与PQC可以有着不同的应用场景，并互为补充。前者偏重于高价值、高安全等级资产（如骨干网）的保护，后者则可以像RSA一样，普及应用在现有的信息基础设施各个方面。

目前，人们普遍认为成熟的量子计算机仍然需要数年乃至数十年时间才会出现。但密码学家认为，如果当前不采取实质性预防措施，网络安全体系的崩溃很可能就是不远将来的确定性事件，而且量子计算威胁的前溯性还将使网络安全防御者面临更加复杂的局面。

例如，2018年美国国家科学院的一份研究报告指出，一种广泛使用的加密方法被证明存在缺陷，但它耗时10多年时间才完全退出。考虑到量子计算的发展速度，我们需要提前应对这种新的安全威胁。

关于后量子密码的意义，荆继武教授用了一个形象的比喻：“量子算法很早就提出来了，但量子计算机没制造出来，这相当于算法口诀出来了，算盘没有造出来。为了防患于未然，要提前设计后量子密码算法。”

参考资料：

https://zhuanlan.zhihu.com/p/45393166

https://mp.weixin.qq.com/s/woMcOKH-9HUppVIbF8ms6A

https://mp.weixin.qq.com/s/2Fc5R4_K1grENO4Siy7p0A

-End-

1930年秋，第六届索尔维会议在布鲁塞尔召开。早有准备的爱因斯坦在会上向玻尔提出了他的著名的思想实验——“光子盒”，公众号名称正源于此。