公钥密码学能在量子计算机中生存吗？

Question

量子计算是以量子物理的叠加原理为基础的。普通计算机中的比特要么是0，要么是1。量子物理学允许比特处于0和1的叠加，同样地，薛定谔的猫可以是“活着”和“死亡”的叠加。

我的问题是:公钥密码体制能否在量子计算机中生存？

Answer 1

公钥密码学能在量子计算机中生存吗？

是。

由于运行Shor算法的功能足够强大的量子计算机，所有当前的PKC实现迟早都是不安全的。

但目前已有一种后量子PKC算法：超同生键交换。这是一个可能的候选后量子PKC，这个或一个笑脸算法将使用一旦强大的量子计算机存在。

Answer 2

目前常用的公钥密码体制是基于因子分解和/或离散对数的严格假设。

利用量子计算机的Shor算法有效地解决了这两个问题。

如果有人建立了一台量子计算机，能够运行数千个量子比特，并且能够在没有退相干的情况下对它们进行足够的运算，那么它就会破坏包括椭圆曲线变体在内的RSA和diffie-hellman。

这会破坏所有常用的公钥加密，但不会破坏所有已知的公钥加密。还有其他的不对称算法，例如基于格点问题的算法，即使在量子计算机面前，这些算法也被认为是安全的。