什么是后量子密码

姓名：王镭璋

学号：19011110177

转载自：https://zhuanlan.zhihu.com/p/45393166

【嵌牛导读】后量子密码，作为未来 5-10 年逐渐代替 RSA、Diffie-Hellman、椭圆曲线等现行公钥密码算法的密码技术，正被越来越多的人所了解。

【嵌牛鼻子】后量子密码，量子计算机 

【嵌牛提问】进入后量子时代以后，我们的网络和信息系统还安全吗？

什么是后量子密码?

后量子密码，是[能够抵抗量子计算机对现有密码算法攻击的]新一代密码算法。

所谓“后”，是因为量子计算机的出现，现有的绝大多数公钥密码算法（RSA、Diffie-Hellman、椭圆曲线等）能被足够大和稳定的量子计算机攻破，所以可以抵抗这种攻击的密码算法可以在量子计算和其之后时代存活下来，所以被称为“后”量子密码。也有人称之为“抗量子密码”，说的都是一个意思。英文中的表述是："Post-quantum Cryptography (PQC)"，或者 "Quantum-resistant cryptography"。

为什么需要后量子密码？

这都要从密码学和量子计算机说起。(这里不会过多注重细节，只对结论进行简单表述，例如：这里不会涉及量子计算机的原理、建造等)

详细的完整解释较为复杂，那这里直接介绍核心的结论：

1.量子计算机很强大，但利用其强大算力的前提是：存在能高效解决问题的量子算法，否则量子计算机没什么用，反而因为其高昂的成本带来劣势。数据：5 量子比特的量子计算机造价在千万美元左右

2.量子计算机现有的一些强大算法/应用包括：密码算法安全性、数学计算、机器学习等

3.对于密码算法安全性，主要是针对公钥密码算法：

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

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

4.对于公钥密码算法，量子计算机对安全性的影响：

4.1完全攻破目前广泛使用的公钥密码算法

4.2增大参数的长度没有用。有人说：把 RSA 的长度从 1024 加到 2048 比特甚至更长，不就安全了吗？答案是：对于现有的经典计算机和算法，这样是可以的。但对于量子计算机和算法，这是徒劳的（除非 RSA 的长度增大到 1GB 或更长。但这样的话，算法还能用吗？对于其他算法呢？）

4.3需要全新的公钥密码算法

5.对于对称密码算法，量子计算机对安全性的影响：

5.1降低现有算法的安全性：安全性从 k-bit 降低为 k/2-bit

5.2增大参数的长度有用

5.3把密钥长度或哈希的长度加倍即可，例如：AES-128 升级至 AES-256，SHA-256 升级至 SHA-512 等。但这并不是必须的，原因后面会进行介绍

6.攻破 RSA-2048 的预计时间和开销：2030 年，量子计算机，10 亿美元，核电站 (PQCrypto 2014, Matteo Mariantoni 的预估)

关于量子计算机，再介绍几个结论：

1.量子比特数量重要，但更重要的是质量。目前建造的量子计算机（例如 Google 的 72 qubit 芯片）中，qubit，也就是量子物理比特的质量很差。由于量子相干等物理机制，必须引入纠错机制，但需要成百上千个量子物理比特进行纠错，来实现一个量子逻辑比特的功能

2.攻破现有的公钥密码算法需要几千甚至几万个逻辑比特。结合上面一点可以看到，建造量子计算机仍处在很初级的阶段

3.D-Wave 建造的 D-Wave 2000Q “量子计算机” 实际上是量子退火算法的，并不是真正意义上的普遍适用的量子计算机

4.对于量子算法（例如 Grover），需要指数级别的内存，因此 Grover 算法的威胁不如 Shor 的算法那么紧迫

用 NIST 后量子密码团队负责人 Dustin Moody 在 AsiaCrypt 2017 会议上的 Talk 概括一下：

1.公钥密码算法：需要后量子密码算法代替

2.对称密码算法：不那么紧迫需要新算法代替。可以通过调整参数解决

对后量子密码算法的需求是什么？有多急迫？

我们需要什么？

显然，是后量子密码算法。更准确的说，是后量子密码技术标准。密码实践中的一个重要结论是：不要自己造轮子（除非你是大佬）。我们现在使用 RSA、Diffie-Hellman、椭圆曲线等算法正是在被定为国际标准后，才逐渐进入应用领域的。

后量子密码算法应该：

1.安全：不仅要在现在的计算条件下安全，也要在量子计算机下安全

2.运行速度快：现有的结果显示，相同安全强度下，后量子密码的计算速度可以超越现有公钥密码的计算速度

3.通信开销合理：实践中几乎不会使用一个公钥/密文大小达到几 M 甚至更大的算法。目前的 RSA-2048 公钥大小约为 256 bytes，椭圆曲线大约为 64 bytes。最好的后量子密码算法的公钥大小在 1KB 左右

4.可被用作现有算法和协议的直接代替，例如：公钥加密、密钥交换、数字签名等

5.更广应用场景：例如：同态加密 (Homomorphic Encryption)、属性加密 (Attribute-based Encryption)、函数加密 (Functional Encryption)、不可区分混淆 (Indistinguishability Obfuscation) 等高级密码学应用

什么时候需要？

这是不容易取得一致结论的地方，主要原因在于：

1.对大型且稳定的量子计算机被建造出来的时间预估：未来 10 年左右

2.新一代密码算法需要多久被确定，以及在真实世界中被应用

直观的结论是：我们要在现有密码算法被攻破前做好准备，尽管什么时间被攻破无人能给出准确的时间。做好准备是指，后量子算法从研究到真正被实际应用和部署，而非局限在学术界的研究领域。

值得注意的是，2015 年 8 月，美国国家安全局 (NSA)呼吁迁移至可以抵抗量子计算机攻击的算法。有意思的是，作为破解加密通讯和密码算法的最大组织，NSA 站出来号召采用后量子密码算法。不知道他们是不是已经在现有的密码破解领域取得了极大的突破？

后量子密码的研究现状如何？

概况

密码学界很早就在研究可以抵抗量子计算机攻击的密码算法，最早可以追溯到 1978/9 年的 McEliece 加密、 Merkle 哈希签名等。但在那时，量子计算机对密码算法的威胁并没有很明确，也没有“后量子”的概念。所以直到最近十几年，后量子密码的重要性逐渐显现出来。"Post-quantum" 的概念

对后量子密码技术的研究和标准制定有以下重要参与方：

1.美国国家标准技术研究所 (NIST)。NIST 早在 2012 年启动了后量子密码的研究工作，并于 2016 年 2 月启动了全球范围内的后量子密码标准征集，并于 2017.11.30 截止草案提交。2018 年 4 月在 Florida 举办了第一届 PQC 标准化会议。NIST 预计在未来 5 年左右，确定新一代公钥密码算法标准

2.欧盟：PQCRYPTO 项目

3.欧洲电信标准化协会 (ETSI)：ETSI 也在寻求制定新一代后量子密码标准。ETSI 已举办了 6 届 workshop。2018 年的 workshop 将于 11 月在北京举行

4.互联网工程任务组 (IETF)

5.美国电气和电子工程师协会 (IEEE)

NIST 后量子密码标准征集

NIST PQC 标准征集工作与 2016 年正式启动。NIST 主要聚焦于以下 3 类后量子密码算法的征集：加密、密钥交换、数字签名。截至 2017.11.30 提交截止，NIST 共收到 82 个算法草案。在进行初步筛选后，NIST公布了 69 个“完整且适合”的草案。

在 69 个候选草案中，主要包括以下 4 种数学方法构造的后量子密码算法：

1.格 (Lattice-based)

2.编码 (Code-based)

3.多变量 (Multivariate-based)

4.哈希 (Hash-based)

结语

后量子密码算法，作为未来 10 年最为重要和前沿的密码技术，将对现有的公钥密码体制产生极为重要而深远的影响。作为 RSA、Diffie-Hellman、椭圆曲线等现行公钥密码算法的代替品，提早理解算法及其应用场景对于未来的信息安全和密码学具有重要的意义。