使用经典密码算法的大密钥会胜过量子计算机吗？

Question

这纯粹是一个理论问题。每个人都在谈论量子密码术是下一件大事，因为量子计算机将比我们今天拥有的计算机快得多。

因此，根据我的理解，量子计算机的计算速度要大得多。

我的问题是，为什么我们不能用巨大的密钥来加密数据，而不是寻找新的算法来超越量子计算机的计算速度呢？

Answer 1

对于对称密码学而言，与目前的做法(例如从128位到256位)相比，将密钥大小翻一番是非常有道理的，它提供了足够的保护，防止能够在大型输入上运行格罗弗算法 (或类似的)的假想量子计算机。与在经典计算机上进行暴力密钥搜索相比，O(2^{n/2})需要对n-bit密钥进行O(2^n)搜索。

许多非对称密码算法，包括所有常用的密码算法(RSA加密和签名、Diffie-Hellman密钥交换、ElGamal加密、Schnorr签名、DSA、ECDH、ECDSA、ECIES、EdDSA.)。在原则上，容易受到一台假设的量子计算机的攻击，该计算机能够在大型输入上运行Shor算法，该计算机使用资源，并且只在密钥位n的数目中工作多项式。这在对称密码学中不起作用，因为Shor的算法在假定公钥与对称密钥之间存在算术关系的情况下，从公钥中派生出私钥，而在对称密码学中，对称密钥与其他对手之间不存在这种关系。由于多项式增长，显然的高安全性将需要不实际的大RSA，甚至ECC密钥；这是在NIST后量子密码第1轮的两个RSA条目中量化的。

不过，增加普通非对称密码系统的密钥大小确实增加了它们对可用于密码分析的假想量子计算机(国安局术语中与密码相关的量子计算机)的抵抗力。至少，这使得有必要使用比例更一致的量子位元，这是一个障碍。我们还远没有量子计算机对任何与密码相关的预测很难有用。