量子威胁：哪种密码学会消亡，哪种会存活？ （或者：为什么 ZK-STARKs 是后量子安全的？） 之前，我解释了量子计算机是如何工作的： 把解决问题想象成试图逃离一个迷宫。 有许多可能的路径，你需要检查每一条，直到找到出口。这就是经典（非量子）计算机的工作方式。 但量子力学的法则允许做得更好。它们允许一个系统（一堆粒子）并行探索迷宫中的*所有*不同路径。到达出口的路径仍然可行，而通向死胡同的路径则消失。 然后，宇宙随机选择一条可行的剩余路径（这是爱因斯坦不喜欢的部分，他说“上帝不掷骰子”，但实际上他确实在掷）。 这就是量子计算机解决经典计算机需要数百万年才能解决的问题的方式。 但有些类型的密码原语可以被量子计算机破解，而有些则保持安全。 这怎么可能？ 在我之前的解释中，我省略了一个关键部分：并不是所有的迷宫都是一样的。 有些迷宫中，死胡同的路径会消失，只留下通向出口的好路径。 我称这些为“量子简单迷宫”，因为当宇宙为这样的迷宫抽样路径时，它总会是一条通向出口的路径。容易到达迷宫的尽头意味着容易被破解。 然而，在“量子困难迷宫”中，所有路径都保持“活着”，无论它们是通向死胡同还是出口。 对于这样的迷宫，量子计算机并不比经典计算机更好。当上帝掷骰子并选择一条路径时，所有路径——好的和坏的——都有同样的可能性出现。 因此，量子计算机做的类似于经典计算机的事情，随机检查迷宫中的一条路径。 现在你可能在问： 哪些迷宫是量子简单的，哪些不是？...