什么是后量子密码？

Question

后量子密码学是假定攻击者有一台大型量子计算机的密码学；即使在这种情况下，后量子密码系统也力求保持安全。

后量子密码学就像基于格的密码一样，即使量子计算机是可用的，也被设计成安全的。我脑海中闪现的问题是：

• 我们如何定义后量子密码？
• 是什么规范使得它不可能被打破？
• 后量子密码能使它在很长一段时间内不可能被打破吗？

Answer 1

我们如何定义后量子密码？

在这个问题之前的句子中，你几乎包含了一个相对准确的非正式要点：

后量子密码学是假定攻击者有一台大型量子计算机的密码学；即使在这种情况下，后量子密码系统也力求保持安全。

更有趣的问题如下：

是什么规范使得它不可能被打破？

首先，一个小小的澄清:很少有算法在概念上是不可能突破的--最坏的情况下，猜测密钥始终是一种可行的策略(例外是一次性pads和类似的一次性验证器)。因此，这是一个成本问题，而不是可能性问题，也就是说，它需要多少时间才能打败这个系统(除了时间，空间也可以发挥作用)。

后量子密码学通常指不对称算法(密钥协议、公钥加密和数字签名)，这些算法不为Shor算法所知。

还有其他量子算法，但Shor的算法似乎是密码学的主要关注点。

相关的数学问题似乎是“隐藏子群问题”：

隐子群问题(HSP)是数学和理论计算机科学研究的一个课题。该框架捕获了分解、图同构和最短向量等问题。这使得它在量子计算理论中显得尤为重要，因为Shor的保理量子算法实质上等价于有限阿贝尔群的隐子群问题，而其他问题则对应于非阿贝尔群的有限群。隐藏子群问题在量子计算理论中特别重要，原因如下：

• Shor的分解和离散对数的量子算法(以及它的几个扩展)依赖于量子计算机求解有限阿贝尔群的HSP的能力。
• 对于某些非阿贝尔群，HSP的有效量子算法的存在意味着对两个主要问题:图同构问题和格中的某些最短向量问题(SVPs)的有效量子算法。更准确地说，对于对称群的HSP，一个有效的量子算法将给出一个图同构的量子算法。一种有效的二面体群量子算法将给出一种适用于\operatorname{poly}(n)唯一的量子算法。

因此，后量子算法是由不等价于有限阿贝尔群的隐子群问题建立的。

对称算法

对于对称算法，相关的威胁是Grover的算法，它为一般的蛮力搜索提供了一个加速。对此的防御比防范Shor的算法简单得多:只需将键和散列的大小加倍，一切都应该是正常的。

这就是为什么AES-256 (和256位密钥在一般情况下)被推荐用于“长期安全性”--一旦你的对手拥有一台能够运行Grover算法的全尺寸量子计算机，128位密钥可能会以64位的代价被打破。