难以置信又令人兴奋的研究领域：后量子密码指南

对于TLS(安全传输层协议)流量、医学数据库和区块链等许多高安全性应用而言，前向保密(forward secrecy)是绝对必要的。同时，仅仅阻止攻击者立即解密敏感信息是不够的。

本文的威胁模型包含了这样一种情况：攻击者在收集密文之后，可能会花费多年时间来解密密文。在这种情况下，密文的保密性很可能被打破。例如，增加的计算能力和数字理论的突破都会使得攻击当前的密码学体制变得相对容易。然而，除非有人找到一个多项式时间内的算法来分解大整数，否则这种风险对于当前密码学的最佳实践来说是最小的。所以，我们应当更加关注量子计算机，因为它的成功开发将使我们今天使用的大多数加密技术变得不安全。

1、量子计算入门

量子计算机不仅仅是大规模并行的经典计算机。通常认为，由于一个量子比特可以同时占据0和1，那么一个n位量子计算机可以同时处于2n个状态，因此计算NP-complete问题的速度非常快。但事实并非如此，因为测量量子态会破坏大部分原始信息。例如，量子系统可以完全知晓一个物体的动量和位置，但是任何动量的测量都会破坏关于位置的信息，反之亦然。这就是海森堡不确定性原理。因此，实用的量子算法必须包括一系列量子比特的变换，这样，在计算结束时，测量系统的状态就不会破坏所需的信息。事实上，已经表明，不存在任何量子算法可以同时尝试解决某些NP-complete问题并输出正确的输入。换句话说，任何解决经典困难问题的量子算法都是利用手边的困难问题构造的特定算法。目前，有两种这样的算法可以用于密码分析。

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

第二个是Grover的算法，它的时间复杂度为O(√n)。这种算法将从根本上降低对称密钥加密的安全性，因此AES-256将只提供128位的安全性。同样，找到256位哈希函数的原像只需2128次。由于将哈希函数或AES的安全性提高两倍并不是很麻烦，所以Grover的算法不会对对称密码体制构成严重威胁。此外，量子计算机的发明不会影响用于加密的所有伪随机数生成器，除了由Grover的算法引起的O(√n)因子。

后量子算法的分类

后量子密码学研究的是可以在经典计算机上运行的密码体制，但即使对手拥有量子计算机也是安全的。最近，NIST发起了一项后量子密码标准化的进程，目前正在审查第一轮提交的文方案。这些提交的方案中最有希望的是那些基于格(lattices)、isogenies、哈希函数(hash functions)和编码(codes)的密码体制。

在深入研究每一类提交的方案之前，我们简要地总结了每种密码体制固有的权衡，并将其与当前(非后量子)椭圆曲线密码学进行了比较。请注意，编码和isogenies是能够设计数字签名的，但没有向NIST提交这样的方案。

在安全性证明方面，上述任何一种密码体制都不能归约到NP-hard(或NP-complete)问题上。就格和编码而言，这些密码体制是基于轻微修改的NP-hard问题。基于哈希函数的密码体制依赖于良好的哈希函数，并且无需其它的加密假设。最后，基于isogenies的密码体制是基于一个被推测为很难的问题，但与NP-hard问题或之前的加密假设不同。然而，值得一提的是，正如我们不能证明任何经典算法在多项式时间内都是不可破解的(因为P可以等于NP)，同样这也是量子计算机所面临的难题。此外，一个不能归约为NP-hard或NP-complete问题的密码体制并不意味着就要放弃它，例如整数分解和离散对数问题，它们并不被认为是NP-complete问题。

2、格

在所有后量子密码体制中，格是研究最活跃和最灵活的。它们具有很强的安全性，能够进行密钥交换、数字签名，以及构造出像全同态加密这样复杂的算法。尽管格密码体制的优化和安全性都需要非常复杂的数学证明，但基本思想只需要基本的线性代数。假设你有一个如下线性方程组：

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

给定向量a，我们在不知道x的情况下，得到了ax的结果，在查询这个函数足够多次之后，我们可以在短时间内学习f(通过求解上面的方程组)。通过这种方式，我们可以将线性代数问题重新定义为机器学习问题。

现在，假设我们在函数中引入了少量噪音，即在x和a相乘之后，我们加上一个误差项e，然后整体模上一个(中等大小的)素数 q，最后我们包含噪音的神秘函数看起来是这样的：

学习这种带噪音的神秘函数已经在数学上被证明是极其困难的。直觉告诉我们，在这种情况下使用高斯消元，它的每一步都会使误差项e变得越来越大，直到它超过关于函数的所有有用信息。在密码学文献中，这被称为错误学习问题(LWE)。

基于LWE的密码学之所以被称为是基于格的密码学，是因为LWE的困难性证明依赖于这样一个事实，即在格中找到最短向量，已知它属于NP-hard问题。在这里，我们不会深入讨论格的数学问题，但我们可以把格看作是n维空间的平铺图：

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

在讨论如何使用LWE进行抗量子密码研究之前，我们应该指出的是LWE本身并不是NP-hard问题。它不是直接归约为SVP，而是归约为SVP的近似值，根据推理，它实际上不是NP-hard问题。尽管如此，目前还没有多项式(或次指数)时间内的算法来求解LWE。

现在让我们使用LWE问题来构建一个实际的密码体制。最简单的方案是由Oded Regev在他最初的论文中构造的，同时他也证明了LWE问题的困难度。这里，密钥是一个n维的整系数模q的向量，也就是上面提到的LWE私钥。公钥是前面讨论的矩阵A，以及LWE函数的输出向量。

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

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

直观地说，我们已经求解了LWE函数(我们知道它很难被破解)的值，并在这个函数的输出中编码了m。

解密是有效的，因为知道了LWE私钥就将允许接收方收回消息，外加一个小的错误项。

正确选择错误分布后，它将不会使消息失真超过q/4。接收方可以测试输出是否接近于0或q/2 mod q，并相应地解码出m。

该体制的一个主要问题是它需要很大的密钥。要加密一位消息，需要在安全参数中使用大小为n2的公钥。然而，格密码体制的一个吸引人的方面是它们的速度非常快。

自从Regev的第一篇论文发表以来，围绕基于格密码体制的研究进行了大量工作。其中关于改进其实用性的一个关键突破是Ring-LWE，Ring-LWE是LWE问题的一个变体，其中密钥是由若干多项式表示的。这导致了密钥大小的二次减少，加速了加密和解密，仅使用n*log(n)次操作(使用快速傅立叶变换，FFT)。

NIST PQC标准考虑了许多基于格密码体制的方案，特别值得一提的两个基于格构造的方案是Kyber和Dilithium。

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

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

3、编码

纠错码的研究在计算机科学文献中有着悠久的历史，可以追溯到Richard Hamming和Claude Shannon的突破性研究。虽然我们甚至无法在一篇简短的博文中触及这一深层领域的表层，但我们给出了一个快速的概述。

在传递二进制消息时，错误可能以位翻转的形式出现。纠错码提供了以牺牲消息紧凑性为代价来承受一定数量的位翻转的能力。例如，我们可以通过编码将0(000)和1(111)来防止单比特位的翻转。这样接收方就能通过对三个比特位进行多数表决的方式确定101实际上是111，或者001是0。但该编码不能纠正两个位被翻转的错误，因为当111变成001时，解码结果为0，而不是1。

纠错码中最为突出的是线性码，可以用k * 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。目前正在尝试使用一种称为准循环中等密度奇偶校验码(quasi-cyclic moderate density parity-check codes)的特殊编码，这种编码可以比Goppa码更简洁地表示，但这些编码的安全性比Goppa码研究得要少。

4、Isogenies

椭圆曲线密码学领域因使用大量晦涩难懂的数学理论而臭名昭著。isogenies更是如此。在椭圆曲线密码学中，我们使用Diffie-Hellman型协议来获取共享的秘密，但是我们不是将群中元素提升到某个幂，而是遍历椭圆曲线上的点。在基于isogenies的密码学中，我们再次使用Diffie-Hellman型协议，但不是遍历椭圆曲线上的点，而是通过一系列椭圆曲线。

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

现在，我们来看看这个图，它是通过检查从起始曲线得到的所有的isogenies，然后是这些曲线的所有isogenies，以此类推。这张图被证明是高度结构化的，因为如果我们从第一个曲线开始随机游走，碰到另一个曲线的概率会很小(除非我们呈指数级地走很多步)。在数学术语中，我们说通过检查所有这些isogenies生成的图是一个扩展图(也是Ramanujan)。这种扩展特性正是使基于isogenies的密码学安全的原因。

对于Supersingular Isogeny Diffie-Hellman(SIDH)方案，私钥是一条由isogenies构成的链，公钥是曲线。当Alice和Bob组合这些消息时，他们得到的曲线是不同的，但是有相同的不变量j。对于密码学来说，j是什么并不重要，重要的是，一旦Alice和Bob完成密钥交换，就可以很容易地计算出这个数字。

与其他后量子方案相比，基于isogeny的密码学拥有非常小的密钥大小，公钥只使用330bytes。不幸的是，在本文讨论的所有技术中，它们是最慢的，在密钥生成和共享秘密计算中都需要11-13毫秒。然而，他们确实支持完美的前向保密，这是其他后量子密码体制所不具备的。

5、基于哈希的签名

已经有很多关于基于哈希的签名的介绍，因此我们将对它们进行简单的讨论。简而言之，哈希签名使用哈希函数的输入作为私钥，输出作为公钥。这些密钥仅适用于一个签名，因为签名本身包含了私钥的一部分。这种极端低效的签名方案通常使用Merkle树来减少空间消耗(是的，与比特币中使用的Merkle树相同)。

遗憾的是，无法使用哈希构造KEM或公钥密码方案。因此，基于哈希的签名并不是一个完整的后量子密码解决方案。此外，它们不是空间有效的;一个比较有前途的签名方案是SPHINCS，它产生的签名大小为41kb，公钥/私钥大小为1kb。另一方面，基于哈希的方案非常快，因为它们只需要计算哈希函数。它们还具有非常强的安全性证明，仅仅基于存在具有抗碰撞和抗原像性的哈希函数的假设。由于没有迹象表明像SHA3或BLAKE2这样当前广泛使用的哈希函数容易受到这些攻击，因此基于哈希的签名是安全的。

6、小贴士

后量子密码学是一个令人难以置信又令人兴奋的研究领域，在过去的十年里已经取得了巨大的进展。尽管这篇文章中描述的四种密码体制受到了学术界的广泛关注，但没有一种密码体制得到NIST的批准，因此目前不推荐用于一般用途。许多方案的最初版本都不具备性能，并且受到各种优化的影响，这些优化可能会影响安全性，也可能不会影响安全性。事实上，多个为McEliece体制使用更节省空间而设计的编码方案都已经被证明是不安全的。就目前而言，从后量子密码体制中获得最佳安全性需要牺牲一定的空间或时间。基于格密码学的研究在灵活性方面是最有前途的(签名和KEM和全同态加密)，但其所基于的假设只是经过了几年的深入研究。目前，最安全的做法是将McEliece与Goppa码一起使用，因为它已经经受了几十年的密码分析。

然而，每个用例都是唯一的。如果您认为您可能需要后量子密码，请与您关系不错的密码学专家联系。其他人应该等待NIST完成后量子密码的标准化。