Skip to content
ecdsa.com

Grover's algorithm

Lov Grover's 1996 quantum search algorithm, which finds a marked item among N in about √N steps and therefore at most halves the effective bit security of symmetric keys and hash preimages.
Also written asGrover's algorithmGrover searchquantum search

Against AES-128 it would take on the order of 2⁶⁴ sequential quantum iterations, but each iteration is a deep, error-corrected AES circuit, and the speed-up does not parallelize well (splitting the search across k machines only gains √k). NIST therefore treats AES-128 as category 1 and does not require doubling symmetric key sizes; NIST IR 8547 keeps AES-128, SHA-256 and SHA-3 in service.

For collision search quantum algorithms offer little practical advantage over classical ones once memory costs are counted. Grover is why post-quantum categories are anchored to AES and SHA-2/SHA-3 strengths and why AES-256 is the conservative choice for very long-lived secrets.

Standards and references

All terms