Ameaça Quântica: Qual criptografia morre e qual sobrevive? (Ou: Por que ZK-STARKs são seguros para PQ?) Anteriormente, expliquei como funciona um computador quântico: Pense em resolver problemas como tentar escapar de um labirinto. Existem muitos caminhos possíveis e você precisa verificar cada um 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. Eles permitem que um sistema (um monte de partículas) explore paralelamente *todos* os caminhos diferentes no labirinto. Os caminhos que levam a 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 (essa é a parte que Einstein não gostou, dizendo "Deus não joga dados", só ele realmente joga). É assim que um controle de qualidade resolve problemas que levariam milhões de anos para um computador clássico. 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 em que os caminhos sem saída desaparecem, deixando o universo com apenas um caminho bom que leva a uma saída. Eu chamo esses de "labirintos quântico-fáceis" porque, quando o universo amostra um caminho para esse tipo de labirinto, ele sempre será um caminho que leva a uma saída. Fácil de alcançar o fim do labirinto significa fácil de quebrar. No entanto, em "labirintos quânticos difíceis" todos os caminhos permanecem "vivos", seja chegando 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. Então, 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ânticamente fáceis e quais não são? ...