后量子密码学指南

对于TLS通信、医疗数据库和区块链等高保障应用而言，前向安全性绝对至关重要。仅防止攻击者立即解密敏感信息是不够的，威胁模型还包括对手可能花费多年时间收集密文后进行解密的情况。

前向安全性可能被破坏的一种潜在方式是：计算能力的提升和数论突破的结合使得攻击当前密码学变得可行。然而，除非有人找到分解大整数的多项式时间算法，否则对当前最佳实践的风险很小。我们应该更关注量子计算机的成功开发，因为这样的突破将使我们今天使用的大多数密码学变得不安全。

量子计算入门

量子计算机不仅仅是大规模并行的经典计算机。通常认为，由于量子比特可以同时处于0和1状态，那么n位量子计算机可以同时处于2^n个状态，因此可以极快地计算NP完全问题。但事实并非如此，因为测量量子态会破坏大部分原始信息。

实际上，已经证明不可能存在同时尝试某个NP完全问题的所有解并输出正确输入的量子算法。换句话说，任何解决困难经典问题的量子算法都必须利用问题的特定结构。目前，有两种这样的算法可用于密码分析。

快速分解大数的能力将破坏RSA和基于离散对数的密码学。最快的整数分解算法是通用数域筛法，它在亚指数时间内运行。然而，1994年Peter Shor开发了一种在多项式时间内运行的量子整数分解算法（Shor算法），因此能够破解任何RSA或基于离散对数的密码系统（包括使用椭圆曲线的系统）。这意味着如果有人建造了量子计算机，所有广泛使用的公钥密码学都将不安全。

第二种是Grover算法，它能在O(√n)时间内反演函数。该算法将以平方根因子降低对称密钥密码学的安全性，因此AES-256将仅提供128位安全性。类似地，找到256位哈希函数的原像只需2^128时间。由于将哈希函数或AES的安全性提高两倍并不非常困难，Grover算法对对称密码学不构成严重威胁。

后量子算法类型

后量子密码学是研究可以在经典计算机上运行，但即使对手拥有量子计算机也能保持安全的密码系统。最近，NIST启动了后量子密码学标准化进程，目前正在审查第一轮提交的方案。最有希望的提交包括基于格、同源映射、哈希函数和编码的密码系统。

在深入探讨每类提交之前，我们简要总结每类密码系统固有的权衡，并与当前（非后量子）椭圆曲线密码学进行比较。

表1：经典ECC与提交给NIST的后量子方案比较

在安全证明方面，上述密码系统都没有归约到NP难（或NP完全）问题。对于格和编码，这些密码系统基于对NP难问题的轻微修改。基于哈希的结构依赖于良好哈希函数的存在，并且不做其他密码学假设。最后，基于同源映射的密码学基于一个被认为困难的问题，但与NP难问题或先前的密码学假设不相似。

格密码学

在所有后量子密码学方法中，格密码学是研究最活跃、最灵活的方法。它们具有强大的安全归约，能够进行密钥交换、数字签名，以及更复杂的构造，如全同态加密。

尽管格密码系统在优化和安全证明方面需要极其复杂的数学，但基础思想只需要基本线性代数。假设你有一个形式的线性方程组：

求解x是一个经典的线性代数问题，可以使用高斯消元法快速解决。另一种思考方式是，我们有一个神秘函数，给定向量a，我们看到ax的结果，但不知道x。在足够多次查询这个函数后，我们可以在短时间内学习f（通过解上述方程组）。这样我们可以将线性代数问题重新构建为机器学习问题。

现在，假设我们向函数引入少量噪声，因此在乘以x和a后，我们添加一个误差项e，并将整个结果模一个（中等大小的）素数q。然后我们的噪声神秘函数看起来像：

数学上已证明学习这个噪声神秘函数极其困难。直觉是，在无噪声情况下使用的高斯消元过程的每一步中，误差项变得越来越大，直到掩盖了关于函数的所有有用信息。在密码学文献中，这被称为带误差学习问题（LWE）。

基于LWE的密码学被称为基于格的密码学，因为LWE困难的证明依赖于这样一个事实：在称为格的结构中找到最短向量已知是NP难的。

在Regev的原始论文之后，围绕基于格的密码系统进行了大量工作。提高其实用性的一个关键突破是Ring-LWE的发展，这是LWE问题的一个变体，其中密钥由某些多项式表示。这导致密钥大小二次减少，并将加密和解密加速到仅使用n*log(n)操作（使用快速傅里叶技术）。

在NIST PQC标准考虑的许多基于格的密码系统中，特别值得提及的是Crystals构造：Kyber和Dilithium。

Kyber是一种密钥封装机制（KEM），遵循与上述系统类似的结构，但使用一些花哨的代数数论来获得比Ring-LWE更好的性能。对于合理的安全参数，密钥大小约为1kb（仍然很大！），但加密和解密时间约为0.075毫秒。考虑到这个速度是在软件中实现的，Kyber KEM对于后量子密钥交换似乎很有希望。

Dilithium是一种基于与Kyber类似技术的数字签名方案。其细节超出了本文的范围，但值得提及的是，它也实现了相当好的性能。公钥大小约为1kb，签名为2kb。它性能也相当好。在Skylake处理器上，计算签名所需的平均周期数约为200万。验证平均需要390,000个周期。

编码密码学

纠错码的研究在计算机科学文献中有着悠久的历史，可以追溯到Richard Hamming和Claude Shannon的开创性工作。

最突出的纠错码类型称为线性码，可以由k x n矩阵表示，其中k是原始消息的长度，n是编码消息的长度。通常，在不知道底层线性码的情况下解码消息在计算上是困难的。这种困难支撑了McEliece公钥密码系统的安全性。

在高层次上，McEliece系统中的秘密密钥是来自称为Goppa码的代码类的随机码（表示为矩阵G）。公钥是矩阵SGP，其中S是具有二进制项的可逆矩阵，P是置换矩阵。要加密消息m，发送方计算c = m(SGP) + e，其中e是随机误差向量，恰好具有代码能够纠正的错误数量。要解密，我们计算cP^-1 = mSG + eP^-1，使得mS是G的码字，可以纠正添加的误差项e。通过计算mSS^-1可以轻松恢复消息。

与格密码学一样，基于编码的密码学受限于密钥是大矩阵的事实。使用推荐的安全参数，McEliece公钥约为1mb，私钥为11kb。目前正在进行尝试使用一类称为准循环中等密度奇偶校验码的特殊代码，这些代码可以比Goppa码更简洁地表示，但这些代码的安全性研究不如Goppa码充分。

同源映射密码学

椭圆曲线密码学领域因使用相当多的奥秘数学而有些 notorious。同源映射将这一点提升到了一个全新的水平。在椭圆曲线密码学中，我们使用Diffie-Hellman类型协议来获取共享秘密，但不是将群元素提升到某个幂，而是在椭圆曲线上遍历点。在基于同源映射的密码学中，我们再次使用Diffie-Hellman类型协议，但不是遍历椭圆曲线上的点，而是遍历一系列椭圆曲线本身。

同源映射是一种将一个椭圆曲线转换为另一个椭圆曲线的函数，使得第一个曲线的群结构反映在第二个曲线中。对于那些熟悉群论的人来说，它是一个群同态，具有一些处理每个曲线几何的附加结构。当我们将注意力限制在超奇异椭圆曲线（这里不定义）时，保证每个曲线都有固定数量的同源映射到其他超奇异曲线。

现在，考虑通过检查从起始曲线出发的所有这种形式的同源映射，然后从那些曲线出发的所有同源映射，依此类推所创建的图。这个图结果是高度结构化的，因为如果我们从第一个曲线开始随机游走，命中特定其他曲线的概率可以忽略不计（除非我们采取指数级多的步骤）。用数学术语来说，我们说通过检查所有这些同源映射生成的图是一个扩展图（也是Ramanujan图）。这种扩展特性正是基于同源映射的密码学安全的原因。

对于超奇异同源Diffie-Hellman（SIDH）方案，秘密密钥是一系列同源映射，公钥是曲线。当Alice和Bob组合这些信息时，他们获得的是不同但具有相同j不变量的曲线。对于密码学的目的来说，j不变量是什么并不那么重要，而是它是一个数字，Alice和Bob在完成密钥交换后都可以轻松计算。

基于同源映射的密码学与其他后量子方案相比具有极小的密钥大小，公钥仅使用330字节。不幸的是，在本文讨论的所有技术中，它们是最慢的，密钥生成和共享秘密计算都需要11-13毫秒。然而，它们支持完美前向安全性，这是其他后量子密码系统所不具备的。

基于哈希的签名

已经有许多友好的基于哈希的签名介绍，因此我们对它们的讨论保持相当高层次。简而言之，哈希签名使用哈希函数的输入作为秘密密钥，输出作为公钥。然而，这些密钥仅适用于一个签名，因为签名本身揭示了部分秘密密钥。基于哈希的签名的这种极端低效导致使用Merkle树来减少空间消耗（是的，与比特币中使用的相同Merkle树）。

不幸的是，不可能从哈希构造KEM或公钥加密方案。因此，基于哈希的签名不是完整的后量子密码学解决方案。此外，它们空间效率不高；更有希望的签名方案之一SPHINCS产生41kb的签名和1kb的公钥/私钥。另一方面，基于哈希的方案非常快，因为它们只需要计算哈希函数。它们还具有极强的安全证明，仅基于存在抗碰撞和原像抵抗的哈希函数的假设。由于没有迹象表明当前广泛使用的哈希函数（如SHA3或BLAKE2）容易受到这些攻击，基于哈希的签名是安全的。

要点

后量子密码学是一个极其令人兴奋的研究领域，在过去十年中取得了巨大增长。虽然本文描述的四类密码系统受到了大量学术关注，但都没有得到NIST的批准，因此尚未推荐普遍使用。许多方案在原始形式上性能不佳，并且经历了各种可能影响安全性的优化。事实上，几次尝试为McEliece系统使用更空间高效的代码已被证明是不安全的。就目前而言，从后量子密码系统中获得最佳安全性需要牺牲一定量的空间或时间。

环格密码学在灵活性方面（签名和KEM，还有全同态加密）是最有希望的工作途径，但其所基于的假设仅被深入研究了几年的时间。目前，最安全的选择是使用带有Goppa码的McEliece，因为它经受了几十年的密码分析。

然而，每个用例都是独特的。如果你认为可能需要后量子密码学，请联系你附近的密码学家。其他所有人都应该等待NIST完成其标准化过程。