Amenaza Cuántica: ¿Qué criptografía muere y qué sobrevive? (O: ¿Por qué los ZK-STARKs son seguros para PQ?) Anteriormente, expliqué cómo funciona un ordenador cuántico: Piensa en resolver problemas como intentar escapar de un laberinto. Hay muchos caminos posibles y tienes que revisar cada uno hasta encontrar la salida. Así es como funciona un ordenador clásico (no cuántico). Pero las leyes de la mecánica cuántica permiten hacerlo mejor. Permiten que un sistema (un montón de partículas) explore en paralelo *todos* los caminos diferentes del laberinto. Los caminos que llevan a una salida siguen siendo viables, mientras que los que llevan a un callejón sin salida desaparecen. Luego, el universo elige al azar uno de los caminos viables que quedan (esta es la parte que a Einstein no le gustó, decir "Dios no juega a los dados", solo él realmente lo hace). Así es como una QC resuelve problemas que a un ordenador clásico le llevaría millones de años resolver. Pero hay tipos de primitivas criptográficas que pueden ser rompidas por un ordenador cuántico, y otras que permanecen seguras. ¿Cómo es esto posible? En mi explicación anterior omití una parte crucial: no todos los laberintos son iguales. Hay algunos laberintos en los que los caminos sin salida desaparecen, dejando al universo solo un buen camino que llega a una salida. Llamo a esto "laberintos cuántico-fáciles" porque cuando el universo muestrea un camino para ese laberinto, siempre será un camino que lleva a una salida. Fácil de alcanzar al final del laberinto significa fácil de romper. Sin embargo, en los "laberintos cuánticos" todos los caminos permanecen "vivos", ya sea que lleguen a un callejón sin salida o a una salida. Para un laberinto así, un ordenador cuántico no es mejor que un ordenador clásico. Cuando Dios lanza un dado y elige un camino, todos los caminos —buenos y malos— tienen la misma probabilidad de aparecer. Así, un ordenador cuántico hace el análogo de un ordenador clásico, comprobando aleatoriamente un solo camino en el laberinto. Ahora probablemente te estés preguntando: ¿Qué laberintos son cuánticamente fáciles y cuáles no? ...