后量子密码学指南

对于许多高保障应用，如TLS流量、医疗数据库和区块链，前向保密性至关重要。仅防止攻击者立即解密敏感信息是不够的，威胁模型还包括对手可能花费多年时间解密已收集的密文。前向保密性可能被破坏的一种潜在方式是计算能力的增加和数论突破的结合，使得攻击当前密码学变得可行。然而，除非有人找到分解大整数的多项式时间算法，否则对当前最佳实践的风险很小。我们更应该关注量子计算机的成功开发，因为这样的突破将使我们现在使用的大多数密码学变得不安全。

量子计算入门

量子计算机不仅仅是高度并行的经典计算机。通常认为，由于量子比特可以同时处于0和1状态，因此n位量子计算机可以同时处于2^n种状态，从而极快地计算NP完全问题。但事实并非如此，因为测量量子态会破坏大部分原始信息。例如，量子系统完全了解物体的动量和位置，但对动量的任何测量都会破坏位置信息，反之亦然。这被称为海森堡不确定性原理。因此，成功的量子算法包括一系列量子比特的变换，使得在计算结束时，测量系统状态不会破坏所需信息。事实上，已经证明不可能存在一种量子算法，同时尝试某个NP完全问题的所有解并输出正确输入。换句话说，任何用于解决困难经典问题的量子算法都必须利用问题的特定结构。如今，有两种这样的算法可用于密码分析。

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

第二种是Grover算法，它能够在O(√n)时间内反转函数。该算法会将对称密钥密码学的安全性降低一个根因子，因此AES-256仅提供128位的安全性。类似地，找到256位哈希函数的原像仅需2^128时间。由于将哈希函数或AES的安全性提高一倍并不非常 burdensome，Grover算法对对称密码学不构成严重威胁。此外，除了Grover算法带来的O(√n)因子外，建议用于密码学的伪随机数生成器都不会受到量子计算机发明的影响。

后量子算法类型

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

在深入探讨每类提交之前，我们简要总结了每类密码系统固有的权衡，并与当前（非后量子）椭圆曲线密码学进行比较。请注意，编码和同源映射能够产生数字签名，但没有此类方案提交给NIST。

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

在安全证明方面，上述密码系统都没有归结为NP难（或NP完全）问题。对于格和编码，这些密码系统基于对NP难问题的轻微修改。基于哈希的构造依赖于良好哈希函数的存在，并且没有其他密码学假设。最后，基于同源映射的密码学基于一个被推测为困难的问题，但与NP难问题或先前的密码学假设不相似。然而，值得提及的是，正如我们无法证明任何经典算法不能在多项式时间内被破解（因为P可能等于NP），被认为对量子计算机困难的问题可能并非如此。此外，密码系统不归结为某个NP难或完全问题本身不应被视为反对它的标志，因为整数分解和离散对数问题不被认为是NP完全的。

格

在所有后量子密码学方法中，格是研究最活跃、最灵活的方法。它们具有强大的安全归约，能够进行密钥交换、数字签名以及更复杂的构造，如全同态加密。尽管格密码系统的优化和安全证明需要极其复杂的数学，但基础思想仅需要基本的线性代数。

假设你有一个形式的线性方程组：

1
2
3
4

a1x1 + a2x2 + ... + anxn = b1
a1x1 + a2x2 + ... + anxn = b2
...
a1x1 + a2x2 + ... + anxn = bm

求解x是一个经典的线性代数问题，可以使用高斯消元法快速解决。另一种思考方式是，我们有一个神秘函数：

1

f(a) = a * x

给定向量a，我们看到a*x的结果，而不知道x。在足够多次查询此函数后，我们可以在短时间内学习f（通过解决上述方程组）。这样，我们可以将线性代数问题重新框架为机器学习问题。

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

1

f(a) = a * x + e mod q

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

基于LWE的密码学被称为基于格的密码学，因为LWE困难的证明依赖于这样一个事实：在称为格的东西中找到最短向量已知是NP难的。我们不会在这里深入探讨格的数学，但可以将格视为n维空间的平铺。

格由坐标向量表示。在上面的示例中，可以通过组合e1、e2和e3（通过正常向量加法）到达格中的任何点。最短向量问题（SVP）说：给定一个格，找到其向量长度最短的元素。直觉上这很困难，因为并非所有给定格的坐标系都同样容易使用。在上面的示例中，我们可以用三个非常长且接近的坐标向量来表示格，这使得找到靠近原点的向量更加困难。事实上，有一种规范的方法可以找到格的“最坏可能”表示。当使用这种表示时，最短向量问题已知是NP难的。

在讨论如何使用LWE制作抗量子密码学之前，我们应该指出LWE本身不是NP难的。它不是直接归结为SVP，而是归结为SVP的一个近似，该近似实际上被推测不是NP难的。尽管如此，目前没有多项式（或次指数）算法来解决LWE。

现在让我们使用LWE问题创建一个实际的密码系统。最简单的方案由Oded Regev在其证明LWE问题硬度的原始论文中创建。这里，密钥是一个n维向量，具有整数条目模q，即上述LWE密钥。公钥是先前讨论中的矩阵A，以及来自LWE函数的输出向量。

此公钥的一个重要特性是，当它乘以向量(-sk,1)时，我们得到误差项，大约为0。

为了加密信息位m，我们取A的随机列之和，并通过添加0（如果m为0）和q/2（如果m为1）在结果的最后坐标中编码m。换句话说，我们选择一个0或1的随机向量x，并计算：

1

c = A * x + (0, ..., 0, m * q/2) mod q

直觉上，我们刚刚评估了LWE函数（我们知道难以破解）并将我们的位编码在此函数的输出中。

解密有效，因为知道LWE密钥将允许接收者获取消息加上小误差项：

1

c * (-sk,1) = e + m * q/2 mod q

当正确选择误差分布时，它永远不会使消息失真超过q/4。接收者可以测试输出是更接近0还是q/2模q，并相应地解码位。

此系统的一个主要问题是它具有非常大的密钥。仅加密一位信息需要大小为n^2的公钥（在安全参数中）。然而，格密码系统的一个吸引人之处是它们非常快。

自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的开创性工作。虽然我们无法在短博客文章中深入探讨这个深奥领域，但我们给出一个快速概述。

在通信二进制消息时，错误可能以位翻转的形式发生。纠错码提供了承受一定数量位翻转的能力，但以消息紧凑性为代价。例如，我们可以通过将0编码为000和1编码为111来防止单一位翻转。这样，接收者可以通过对三个位进行多数表决来确定101实际上是111，或者001是0。此代码无法纠正两个位被翻转的错误，因为111变为001将被解码为0。

最突出的纠错码类型称为线性码，可以由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公钥约为1 mb，私钥为11 kb。目前正在进行的工作试图使用一类称为准循环中等密度奇偶校验码的特殊代码，这些代码可以比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，以及全同态加密）方面是最有前途的工作途径，但其基于的假设仅被深入研究了几