格密链向大家分享了后量子密码指南,其中包含量子计算,后量子密码等知识点,遇到此问题的同学们可以参考下
对于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）的密码体制。
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、格
在所有后量子密码体制中，格是研究最活跃和最灵活的。它们具有很强的安全性，能够进行密钥交换、数字签名，以及构造出像全同态加密这样复杂的算法。尽管格密码体制的优化和安全性都需要非常复杂的数学证明，但基本思想只需要基本的线性代数。假设你有一个如下线性方程组：