后量子密码学指南

对于许多高保障应用（如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完全的。

格

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

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

现在，假设向函数引入少量噪声，使得在乘x和a后，我们添加一个误差项e并将整个结果模一个（中等大小）素数q。然后我们的噪声神秘函数看起来像：
g(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，并计算：
c = (A·x, b·x + m * q/2)
直觉上，我们刚刚评估了LWE函数（已知难以破解）并将我们的位编码在该函数的输出中。

解密有效是因为知道LWE密钥允许接收者获取消息加上小误差项：
c·(-sk,1) = e + m * q/2
当正确选择误差分布时，它永远不会使消息失真超过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类似的技术。其细节超出本博客范围，但值得提及它 also 实现了相当好的性能。公钥大小约为1kb，签名为2kb。它也相当高效。在Skylake处理器上，计算签名所需的平均周期数约为200万次。验证平均耗时39万周期。

编码

纠错码的研究在计算机科学文献中有着悠久历史，可追溯到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，以及全同态加密）方面是最有前途的工作途径，但其基于的假设仅被深入研究了几