Grover's Algorithm
What is Grover's Algorithm?
Grover's AlgorithmA quantum search algorithm that finds a marked item in an unstructured database of N entries in roughly sqrt(N) steps, providing a quadratic speed-up against symmetric ciphers and hash functions.
Grover's Algorithm, introduced by Lov Grover in 1996, is a quantum routine that locates a marked input to a black-box function in O(sqrt(N)) queries instead of the classical O(N). Applied to cryptography, it halves the effective security level of symmetric primitives and hash functions: AES-128 drops to about 64 bits of security, and SHA-256 preimage resistance to about 128 bits. The standard mitigation is simply to double key and digest sizes — for example using AES-256 and SHA-384 or SHA-512 — which keeps a comfortable margin even under Grover-style attacks. Unlike Shor's algorithm, Grover does not break public-key cryptography outright.
● Examples
- 01
Used to estimate post-quantum security of AES-128 versus AES-256 in NIST guidance.
- 02
Cited when justifying migration of HMAC and KDF outputs to 256-bit or larger digests.
● Frequently asked questions
What is Grover's Algorithm?
A quantum search algorithm that finds a marked item in an unstructured database of N entries in roughly sqrt(N) steps, providing a quadratic speed-up against symmetric ciphers and hash functions. It belongs to the Cryptography category of cybersecurity.
What does Grover's Algorithm mean?
A quantum search algorithm that finds a marked item in an unstructured database of N entries in roughly sqrt(N) steps, providing a quadratic speed-up against symmetric ciphers and hash functions.
How does Grover's Algorithm work?
Grover's Algorithm, introduced by Lov Grover in 1996, is a quantum routine that locates a marked input to a black-box function in O(sqrt(N)) queries instead of the classical O(N). Applied to cryptography, it halves the effective security level of symmetric primitives and hash functions: AES-128 drops to about 64 bits of security, and SHA-256 preimage resistance to about 128 bits. The standard mitigation is simply to double key and digest sizes — for example using AES-256 and SHA-384 or SHA-512 — which keeps a comfortable margin even under Grover-style attacks. Unlike Shor's algorithm, Grover does not break public-key cryptography outright.
How do you defend against Grover's Algorithm?
Defences for Grover's Algorithm typically combine technical controls and operational practices, as detailed in the full definition above.
What are other names for Grover's Algorithm?
Common alternative names include: Grover search.
● Related terms
- cryptography№ 846
Post-Quantum Cryptography
Classical cryptographic algorithms designed to remain secure against attacks by both classical and large-scale quantum computers.
- cryptography№ 020
AES (Advanced Encryption Standard)
A NIST-standardized 128-bit block cipher with 128-, 192- or 256-bit keys, designed by Daemen and Rijmen and used as the dominant symmetric cipher worldwide.
- cryptography№ 247
Cryptographic Hash Function
A deterministic one-way function that maps arbitrary-length input to a fixed-length digest, designed to be collision-, preimage-, and second-preimage-resistant.
- cryptography№ 1036
Shor's Algorithm
A quantum algorithm that factors large integers and computes discrete logarithms in polynomial time, breaking RSA, Diffie-Hellman, and elliptic-curve cryptography on a sufficiently large quantum computer.
- cryptography№ 1121
Symmetric Encryption
An encryption scheme in which the same secret key is used for both encryption and decryption, offering high speed and strong confidentiality when the key is shared securely.
- cryptography№ 890
Quantum Cryptography
Cryptography that uses quantum-mechanical properties — typically of photons — to achieve security guarantees impossible with classical communication alone.