“量子安全”算法与当前的“安全”密码算法(前量子算法)有什么根本区别？

Question

我最近读到，正在开发用于加密/散列的“量子安全”算法。

据推测，这些算法将与目前使用的“非量子安全”算法(RSA、DH、AES、ChaCha20、Poly1305、SHA3 2/SHA3 3等)有着根本的区别。

哪些基本差异使算法成为“量子安全”？在非量子计算机中，量子安全算法是否更加脆弱？

Answer 1

所以我猜你指的是量子后算法。这个话题不是关于散列(SHA3等)。或分组密码(AES等)因为两者在PQ场景中都有很好的理解，而且看起来都是可证明的安全的(而且可能需要增加位数，因为是格罗弗算法)，但这是关于非对称加密的。

当我们谈论非对称密码学时，我们基本上是说，你有一个公钥和一个私钥，你可以用其中一个加密，然后用另一个加密。非对称密码学也是签名的基础。

因此量子安全(或后量子)-algorithms主要关注的是非对称密码学。

目前使用的非对称密码的主要区别在于算法的潜在问题。以RSA为例，它的硬度来源于这个问题，很难找到足够多的素数。然而，在一台量子计算机上，这个问题可以用Shor算法在多项式时间内解决，因而会被打破。Shor算法也可以用来解决离散对数问题，在现代密码学中也发挥着重要的作用。

这些量子安全算法试图利用不同的潜在问题(基于格、码、.)目前还不知道来自量子(和非量子)计算机的算法能解决这些问题。

目前正在出现一个NIST竞赛，它试图找到并标准化这类算法。有几篇关于这个话题的论文和报告，如果你想深入挖掘的话。

编辑: Maarten指出了Tanja关于problems中潜在问题的视频，我将链接这里。