Como exatamente o algoritmo de Grovers “quebra” a criptografia de chave simétrica?

Question

Como exatamente o algoritmo de Grovers "quebra" a criptografia de chave simétrica? Eu pesquisei na internet e descobri que isso poderia tornar o comprimento da chave efetivamente igual à metade, o que significa que você só precisava dobrar o lenth de sua chave para que a criptografia fosse viável novamente. Mas como exatamente poderia força bruta a senha?

Answer 1

O algoritmo de Grover é um solucionador de Circuito SAT que encontra uma atribuição satisfatória em torno$2^{n/2}$ avaliações do circuito, onde $n$é o número de entradas. Você pode construir um circuito que recebe uma chave como entrada e verifica se pode descriptografar com êxito um texto cifrado com essa chave (talvez verificando um autenticador), retornando 1 se puder. O algoritmo de Grover, então, fornece uma chave de trabalho em torno$2^{n/2}$ descriptografias onde $n$ é o comprimento da chave.