后量子公钥密码正式启动时间

后量子公钥密码正式启动时间？

　　后量子密码，作为未来 5-10 年逐渐代替 RSA、Diffie-Hellman、椭圆曲线等现行公钥密码算法的密码技术，正被越来越多的人所了解。目前，美国国家标准技术研究所 (NIST) 正在制定的新一代密码技术标准，正是后量子密码标准。

1.1.1，后量子密码是什么？

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

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

1.1.2，为什么需要？

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）对称密码算法：蓝色框，不那么紧迫需要新算法代替。可以通过调整参数解决

1.1.3，我们需要什么样的？

显然，是后量子密码算法。更准确的说，是后量子密码技术标准。密码实践中的一个重要结论是：不要自己造轮子（除非你是大佬）。我们现在使用 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) 等高级密码学应用