“量子后安全”是如何证明/显示的？

Question

由于人们越来越关注量子计算对非对称密码学(RSA、ECC等)的威胁，人们提出了许多“量子抵抗”的替代方案(SPHINCS、McBits等)。在量子计算机的存在下，这些密码系统如何被证明(或论证)是安全的？

这些方案是仅针对有限的量子算法集(Shor算法、Grover算法等)被证明是安全的，还是在某些量子计算理论模型中被证明对所有量子算法都是安全的？

Answer 1

这在原则上类似于如何证明“正常”密码系统。有了一些算法，我们可以将它们简化为一些“困难问题”，但我们不知道这些问题实际上是很难解决的。只是我们不能有效地解决这些问题。例如，Diffie-Hellman问题甚至不知道NP难，更别提P对NP的整个问题了。

同样，我们知道Shor算法加速的一些问题。后量子算法避免了这些问题，并利用Shor的算法不能提供一个简单的解决方案的问题。然而，这并不意味着没有其他算法来解决它们，甚至也不意味着没有办法为它们使用Shor's。(例如，可以将非阿贝尔群中的隐子群问题归结为阿贝尔群中的HSP问题。)

最后，它与对称算法相似。它们是并不是很安全，但经过多年的密码分析，它们就被证明了。