量子计算对椭圆曲线密码有多有效？

Question

我一直在阅读维基百科关于椭圆曲线密码学的网页，我看到了以下内容。

2015年8月，美国国家安全局宣布，由于担心量子计算攻击ECC，计划用新的密码套件取代Suite B。椭圆曲线密码学

我的问题是，ECC对量子计算有多脆弱？

Answer 1

一些广泛使用的ECC密码系统，包括ECDSA和Ed25519，ECDH。在理论上容易受到量子计算的影响，如果它可以用于密码分析(国安局术语中与密码学相关的量子计算机)。这些密码体制是基于一个离散对数问题，并成为次指数的w.r.t。量子计算假设下未知指数的比特大小。

另一方面，有一些可信的基于ECC的密码系统是为后量子安全而设计的，比如赛克。因此，ECC可能仍然是后量子非对称密码术的主流，但以另一种形式存在。

我们不知道什么时候，如果有的话，量子密码启示录可能发生；或如何预测。到目前为止，量子计算机几乎没有比经典计算机做得更好的事情，而且这往往与密码分析无关；比如:模拟特定的量子计算机所处的量子系统，或者(正在争论的)为一类狭窄的优化问题找到一个很好的解决方案。

Answer 2

目前使用的大多数公钥算法都是基于两个数学问题，即大数的因式分解(例如RSA)和离散对数的计算(例如DSA签名和ElGamal加密)。两者具有相似的数学结构，可以用Shor的算法快速打破。最近基于椭圆曲线的算法(如ECDSA)对离散对数问题进行了修改，使得它们在量子计算机上同样弱。有关更多细节，请参阅以下文件的第4节C小节，其中详细描述了上述声明：https://arxiv.org/abs/1804.00200?context=cs：