量子计算下的安全体系

什么是量子计算

量子计算是利用诸如叠加和纠缠等量子力学现象来进行计算。执行量子计算的计算机称为量子计算机。Quantum计算机被认为能够解决某些计算问题，例如整数分解（它是RSA加密的基础），其速度比传统计算机快得多。量子计算的研究是量子信息科学的一个子领域。

量子计算为什么快

在量子计算出现以前，经典计算机采用二进制的比特（用“0”或“1”表示）作为信息存储单位，进而实现各种运算。而经典计算运算过程则是经由对存储器所存数据的操作来实施的。并且，经典计算机无论其存储器有多少位，一次只能存储一个数据，对其实施一次操作只能变换一个数据。因此，在运算时，必须连续实施多次操作，这就是串行计算模式。

与经典计算机不同，量子计算机的信息单元是量子位。量子位最大的特点就是其可以处于“0”和“1”的叠加态，即一个量子位可以同时存储“0”和“1”两个数据，而传统计算机只能存储其中一个数据。比如一个两位存储器，量子存储器可同时存储“00”“01”“10”“11”四个数据，而传统存储器只能存储其中一个数据。

也就是说，n位量子存储器可同时存储2^n个数据，它的存储能力将是传统存储器的2^n倍。因此，一台由10个量子位组成的量子计算机，其运算能力就相当于1024位的传统计算机。而对于一台由250个量子位组成的量子计算机（n=250），它能存储的数据将比宇宙中所有原子的数目还要多。

量子计算机发展成果

目前中美两国是量子计算机主要引领者，以中国“九章”、美国“悬铃木”为代表。

九章

2020年12月，中国科学技术大学宣布该校潘建伟等人成功构建76个光子的，量子计算原型机“九章”， 在实现 “高斯玻色取样”任务的快速求解中，“九章”的运算速度超过目前最快的超级计算机的一百万亿倍。

悬铃木

“悬铃木“（Sycamore），是由谷歌公司于2019年9月研制完成的量子计算原型机。其处理的问题大致可以理解为：判断一个量子随机数发生器是不是真的随机。“悬铃木” 包含53个量子比特的芯片，花了200秒对一个量子线路取样一百万次，而利用当时世界排名第一的超级计算机 “Summit” 完成同样的任务需要一万年。

量子计算机能用来做什么

首先，量子计算机并不是经典计算机的升级换代，它也取代不了现有计算机。如果有人问：是不是用量子计算机打游戏稳赢？是不是用量子计算机看电影一点都不卡？那么很遗憾，量子计算机目前并不能做这些事，甚至计算简单问题时还不如经典计算机。那种认为量子计算机可以在任何问题上都超越经典计算机的观点是有认识误区的。

其次，量子计算机是用来解决经典计算机再怎么升级也解决不了的问题，而不是用更优的方法去解决经典计算机已经能解决的问题。比如走迷宫，每个人遇到一个两岔路口就再喊来一个小伙伴分头走，这个迷宫不用太大，只要所有人在遇到第33个路口还没有找到出口的话，人数就变成了85亿8900万！全地球的人都不够。经典计算所遇到的大困难其实就是指数级增长，也叫作计算复杂性，我们面临的问题虽然是线性增加，解决问题所需要的计算能力却是指数级“大爆炸”。利用万亿次经典计算机分解300位的大数需要15万年，而利用量子计算机只需1秒钟。

国际学术界把量子计算大概分成三个阶段：第一阶段就是造出一台量子计算机，证明在计算某个具体问题上量子计算机可以超越目前最快的超级计算机，“九章”号和“悬铃木”等完成了这个使命，成为展示量子计算优越性的里程碑。第二阶段是希望实现能够操纵数百个量子比特的计算机，也叫量子模拟机或者专用量子计算机，解决若干经典计算机无法胜任的具有重大实用价值的问题。第三阶段是希望可集成的量子比特数目达到百万量级，最终实现可编程的通用量子计算机。

可以说，在相当长一段时间里，经典计算机并不会被取代，而是与量子计算机同在，解决各自擅长的问题，或者量子计算机与超级计算机合体，加速计算一些特别的问题。

我们的密码还安全吗

已知目前超级计算机破解RSA2048密钥需要64亿年， 而“九章”运算速度是现在最快的超级计算机的一百万亿倍，通过简单换算可以得到“九章”破解RSA2048密钥只需要33分钟。那么我们的密码是否已经不安全了？通过“九章”发布两年来，安全圈风平浪静可以看出我们的密码依然还是安全的。因为无论“九章”还是“悬铃木”目前都还只是原型机并不是真正意义上的量子计算机，根本无法运行用于分解大数质因子的Shor算法。具体来说，“九章”目前只可以运行“高斯玻色取样”这单一任务，并不能运行其他量子算法。即使是具备一定编程能力的悬铃木，目前也只是针对随机数的特殊问题，缺乏真正的实用性。

而要实现通用型量子计算机的量产还有非常漫长的道路。“悬铃木”、“九章”号等量子计算机都只能在一个问题上完胜经典计算机。当然即便只是“单项冠军”，量子计算机的发展仍然对密码具有极大的潜在威胁， 据报道，谷歌的Craig Gidney和瑞典斯德哥尔摩KTH皇家理工学院的Martin Ekera一项最新研究成果，演示了量子计算机如何用2000个量子位来计算，他们证明了2048位RSA密码，如何在八个小时被暴力破解。

后量子时代安全如何保证

目前应对量子计算的研究有两个方向：

• 量子通信
• 抗量子密码

量子通信

量子通信作为量子信息研究的主要内容，是目前量子信息领域最具有应用前景的一个部分，它主要研究两个：

• 量子密钥分发
• 量子直接通信

量子密钥分发的安全性由量子力学原理来保证，与攻击者的计算能力无关，在理论上具有无条件的安全性。它与经典的一次一密乱码本相结 合能够组成具有完美安全性的通信系统。

量子直接通信与量子密钥分发不同，量 子直接通信是直接在量子信道中传输秘密消 息，其安全性要求比量子密钥分发更高，不但要求能够探测到窃听者，而且保证在探测到窃听者之前传输的秘密信息不泄漏。

抗量子密码

抗量子密码是能够抵抗量子计算机对现有密码算法攻击的新一代密码算法。因为量子计算机的出现，现有的绝大多数公钥密码算法（RSA、Diffie-Hellman、椭圆曲线等）能被足够大和稳定的量子计算机攻破，所以可以抵抗这种攻击的密码算法可以在量子计算和其之后时代存活下来，所以被称为“后”量子密码，也被为“抗量子密码”。

目前传统的公钥密码算法安全性依赖的数学问题可以被高效的量子算法所解决。由于底层依赖的数学问题被解决，所以这些公钥密码算法不再安全。这些数学问题包括：离散对数 (及椭圆曲线版本)、大整数分解等。这直接影响目前使用的 RSA、Diffie-Hellman、椭圆曲线等算法。著名的量子算法是 1994 年的 Shor's algorithm。对于公钥密码算法，量子计算机对安全性的影响：

• 完全攻破目前广泛使用的公钥密码算法
• 增大参数的长度没有用。有人说：把 RSA 的长度从 1024 加到 2048 比特甚至更长，不就安全了吗？答案是：对于现有的经典计算机和算法，这样是可以的。但对于量子计算机和算法，这是徒劳的（除非 RSA 的长度增大到 1GB 或更长。但这样的话，算法还能用吗？）
• 需要全新的公钥密码算法

关于对称密码算法和哈希函数（例如 AES、SHA1、SHA2 等），虽然有量子算法可以理论上攻破，但这个算法的影响有限，且有很多限制条件。著名的量子算法是 1996 年的 Grover's algorithm。对于对称密码算法，量子计算机对安全性的影响：

• 降低现有算法的安全性：安全性从 k-bit 降低为 k/2-bit
• 增大参数的长度有用
• 把密钥长度或哈希的长度加倍即可，例如：AES-128 升级至 AES-256，SHA-256 升级至 SHA-512 等。但这并不是必须的。

因此抗量子密码算法应该满足：

• 安全：不仅要在现在的计算条件下安全，也要在量子计算机下安全
• 运行速度快：现有的结果显示，相同安全强度下，后量子密码的计算速度可以超越现有公钥密码的计算速度
• 通信开销合理：实践中几乎不会使用一个公钥/密文大小达到几 M 甚至更大的算法。目前的 RSA-2048 公钥大小约为 256 bytes，椭圆曲线大约为 64 bytes。最好的抗量子密码算法的公钥大小在 1KB 左右
• 可被用作现有算法和协议的直接代替，例如：公钥加密、密钥交换、数字签名等
• 更广应用场景：例如：同态加密、属性加密、函数加密 、不可区分混淆等高级密码学应用

下图是 NIST 总结的后量子密码技术和应用栈：

目前实现后量子密码算法主要有以下4种途径：

• 基于哈希 (Hash-based)：最早出现于 1979 年，主要用于构造数字签名。代表算法：Merkle 哈希树签名、XMSS、Lamport 签名等
• 基于编码 (Code-based)：最早出现于 1978 年，主要用于构造加密算法。代表算法：McEliece
• 基于多变量 (Multivariate-based)：最早出现于 1988 年，主要用于构造数字签名、加密、密钥交换等。代表方法/算法：HFE (Hidden Field Equations)、Rainbow (Unbalanced Oil and Vinegar (UOV) 方法)、HFEv- 等
• 基于格(Lattice-based)：最早出现于 1996 年，主要用于构造加密、数字签名、密钥交换，以及众多高级密码学应用，如：属性加密 (Attribute-based encryption)、陷门函数 (Trapdoor functions)、伪随机函数 (Pseudorandom functions)、同态加密 (Homomorphic Encryption) 等。代表算法：NTRU 系列、NewHope (Google 测试过的)、一系列同态加密算法 (BGV、GSW、FV 等)。由于其计算速度快、通信开销较小，且能被用于构造各类密码学算法和应用，因此被认为是最有希望的后量子密码技术。