Algoritmo de Grover
O que é Algoritmo de Grover?
Algoritmo de GroverAlgoritmo quântico de pesquisa que encontra um elemento marcado numa base não estruturada de N entradas em cerca de sqrt(N) passos, oferecendo um ganho quadrático contra cifras simétricas e funções de hash.
O Algoritmo de Grover, apresentado por Lov Grover em 1996, localiza uma entrada marcada de uma função oráculo em O(sqrt(N)) consultas, em vez das O(N) clássicas. Aplicado à criptografia, reduz para metade o nível efetivo de segurança das primitivas simétricas e funções de hash: AES-128 cai para cerca de 64 bits de segurança e a resistência à pré-imagem do SHA-256 para cerca de 128 bits. A mitigação habitual é dobrar o tamanho das chaves e dos resumos — por exemplo, AES-256 e SHA-384 ou SHA-512 —, mantendo uma margem confortável mesmo perante ataques tipo Grover. Ao contrário do algoritmo de Shor, Grover não quebra, por si só, a criptografia de chave pública.
● Exemplos
- 01
Usado para estimar a segurança pós-quântica do AES-128 face ao AES-256 nas orientações do NIST.
- 02
Citado para justificar a migração de HMAC e KDF para saídas de 256 bits ou mais.
● Perguntas frequentes
O que é Algoritmo de Grover?
Algoritmo quântico de pesquisa que encontra um elemento marcado numa base não estruturada de N entradas em cerca de sqrt(N) passos, oferecendo um ganho quadrático contra cifras simétricas e funções de hash. Pertence à categoria Criptografia da cibersegurança.
O que significa Algoritmo de Grover?
Algoritmo quântico de pesquisa que encontra um elemento marcado numa base não estruturada de N entradas em cerca de sqrt(N) passos, oferecendo um ganho quadrático contra cifras simétricas e funções de hash.
Como funciona Algoritmo de Grover?
O Algoritmo de Grover, apresentado por Lov Grover em 1996, localiza uma entrada marcada de uma função oráculo em O(sqrt(N)) consultas, em vez das O(N) clássicas. Aplicado à criptografia, reduz para metade o nível efetivo de segurança das primitivas simétricas e funções de hash: AES-128 cai para cerca de 64 bits de segurança e a resistência à pré-imagem do SHA-256 para cerca de 128 bits. A mitigação habitual é dobrar o tamanho das chaves e dos resumos — por exemplo, AES-256 e SHA-384 ou SHA-512 —, mantendo uma margem confortável mesmo perante ataques tipo Grover. Ao contrário do algoritmo de Shor, Grover não quebra, por si só, a criptografia de chave pública.
Como se defender contra Algoritmo de Grover?
As defesas contra Algoritmo de Grover costumam combinar controles técnicos e práticas operacionais, conforme detalhado na definição acima.
Quais são outros nomes para Algoritmo de Grover?
Nomes alternativos comuns: Pesquisa de Grover.
● Termos relacionados
- cryptography№ 846
Criptografia pós-quântica
Algoritmos criptográficos clássicos concebidos para se manterem seguros contra ataques de computadores clássicos e computadores quânticos de grande escala.
- cryptography№ 020
AES (Advanced Encryption Standard)
Cifra de bloco de 128 bits normalizada pelo NIST com chaves de 128, 192 ou 256 bits, projetada por Daemen e Rijmen e usada como cifra simétrica dominante a nível mundial.
- cryptography№ 247
Função de hash criptográfica
Função unidirecional determinista que mapeia entradas de comprimento arbitrário num resumo de comprimento fixo, resistente a pré-imagens, segundas pré-imagens e colisões.
- cryptography№ 1036
Algoritmo de Shor
Algoritmo quântico que fatora inteiros grandes e calcula logaritmos discretos em tempo polinomial, quebrando RSA, Diffie-Hellman e a criptografia de curvas elípticas num computador quântico suficientemente grande.
- cryptography№ 1121
Cifragem simétrica
Esquema de cifragem em que a mesma chave secreta é usada para cifrar e decifrar, oferecendo alta velocidade e forte confidencialidade quando a chave é partilhada de forma segura.
- cryptography№ 890
Criptografia quântica
Criptografia que utiliza propriedades quânticas, tipicamente de fotões, para obter garantias de segurança impossíveis apenas com comunicação clássica.