Ameaça Quântica: Quais criptografias morrem e quais sobrevivem? (Ou: Por que os ZK-STARKs são seguros contra PQ?) Anteriormente, expliquei como funciona um computador quântico: Pense na resolução de problemas como tentar escapar de um labirinto. Existem muitos caminhos possíveis e você precisa verificar cada um deles até encontrar a saída. É assim que um computador clássico (não quântico) funciona. Mas as leis da mecânica quântica permitem fazer melhor. Elas permitem que um sistema (um conjunto de partículas) explore em paralelo *todos* os diferentes caminhos no labirinto. Os caminhos que alcançam uma saída permanecem viáveis, enquanto os que levam a um beco sem saída desaparecem. Então, o universo escolhe aleatoriamente um dos caminhos viáveis restantes (esta é a parte que Einstein não gostava, dizendo "Deus não joga dados", mas ele realmente joga). É assim que um QC resolve problemas que levariam milhões de anos para um computador clássico resolver. Mas existem tipos de primitivas criptográficas que podem ser quebradas por um computador quântico, e outras que permanecem seguras. Como isso é possível? Na minha explicação anterior, omiti uma parte crucial: Nem todos os labirintos são iguais. Existem alguns labirintos nos quais os caminhos sem saída desaparecem, deixando o universo apenas com o bom caminho que leva a uma saída. Eu chamo esses de "labirintos quânticos fáceis" porque, quando o universo amostra um caminho para tal labirinto, sempre será um caminho que leva a uma saída. Fácil de alcançar o final do labirinto significa fácil de quebrar. No entanto, em "labirintos quânticos difíceis", todos os caminhos permanecem "vivos", quer cheguem a um beco sem saída ou a uma saída. Para tal labirinto, um computador quântico não é melhor do que um computador clássico. Quando Deus joga um dado e escolhe um caminho, todos os caminhos – bons e ruins – têm a mesma probabilidade de aparecer. Assim, um computador quântico faz o análogo de um computador clássico, verificando aleatoriamente um único caminho no labirinto. Agora você provavelmente está se perguntando: Quais labirintos são quânticos fáceis e quais não são? ...