用量子计算机实现伪随机生成器的可预测性

Question

在未来，经典的伪随机发生器可能会被强大的量子计算机预测到吗?或者这是否被证明是不可能的？

如果它们是可预测的，科学家们是否知道是否存在量子计算机不可预测的PRG？

Answer 1

经典的密码学伪随机数发生器(CPRNG)的安全性总是基于一些硬性假设，如“因子分解困难”或“碰撞SHA-256函数困难”。

但不是所有人。

例如，blum blum shub很可能被量子计算机打破，但没有人知道如何用量子计算机打破lattice-based cryptography。展示你可以用量子计算机打破所有经典的CPRNG等同于证明BQP=NP，这不是预期的情况。

即使量子计算机确实打破了所有经典的CPRNG，它们也恰好填补了这个空洞。他们enable the creation of "Einstein-certified" random numbers。