# What is Grover’s algorithm?

Grover’s algorithm is a quantum search method that finds one item among N in about the square root of N steps. Against symmetric keys and hashes, it halves the strength in bits, so a 256-bit key keeps about 128 bits of strength against it.

Also called Grover algorithm or quantum search algorithm.

## How it speeds up search

Searching an unsorted list of N items takes about N checks on a classical computer, because nothing points to the right entry. Grover’s method uses quantum interference to build up the amplitude of the right answer, and it needs about the square root of N steps.

That is a quadratic speedup. Shor’s algorithm gains far more, because it reduces factoring and discrete logarithms to polynomial work, where the best classical methods need far more.

## What it does to keys and hashes

- A symmetric key of n bits has 2^n possible values, so a brute-force search takes about 2^n guesses on a classical computer.
- Grover’s method reduces that to about 2^(n/2) steps, so a 256-bit key falls to about 128 bits of work.
- Finding the input behind a hash, called a preimage, is the same kind of search, so a 256-bit hash also falls to about 128 bits of work.
- Doubling the key or hash length restores the original margin against this attack.

## How it compares with Shor’s algorithm

Grover’s method halves the bits of symmetric keys and hashes, while Shor’s algorithm breaks RSA and elliptic-curve keys outright. The fix for Grover is a longer key, and the fix for Shor is a different kind of cryptography.

## In Redacted

In bunker mode, notes, nullifiers, the note tree and every proof transcript use SHA-256, and your account is 256 random bits, kept as 25 words. The halving described above applies to both of those sizes.

More: [Bunker mode](https://redacted.gg/docs/using-redacted/bunker-mode.md)

## Related terms

- [Shor’s algorithm](https://redacted.gg/glossary/shors-algorithm.md): Shor’s algorithm is a quantum method, described by Peter Shor in 1994, that factors large numbers and computes discrete logarithms in polynomial time. A large enough quantum computer running it would break RSA and elliptic-curve signatures such as ECDSA.
- [Quantum computer](https://redacted.gg/glossary/quantum-computer.md): A quantum computer works with qubits, which can hold a combination of 0 and 1 and can be entangled with each other. A cryptographically relevant one would be large and reliable enough to break the public-key cryptography that wallets and websites rely on.
- [Hash function](https://redacted.gg/glossary/hash-function.md): A hash function turns any input into a short fingerprint of fixed size. The same input always gives the same fingerprint, and nobody can work back from it or find two inputs that share one.
- [Post-quantum cryptography](https://redacted.gg/glossary/post-quantum-cryptography.md): Post-quantum cryptography is ordinary cryptography designed to stay secure when large quantum computers exist. It replaces the key exchanges and signatures that Shor’s algorithm breaks, such as RSA and elliptic curves, with schemes built on lattices, hash functions or error-correcting codes.
- [Hash-based signature](https://redacted.gg/glossary/hash-based-signature.md): A hash-based signature proves that the holder of a private key approved a message, and its security rests only on a hash function. Leslie Lamport described the basic idea in 1979, and SLH-DSA, published as FIPS 205 in 2024, is a modern version.

Sources: [A fast quantum mechanical algorithm for database search, Lov Grover, 1996](https://arxiv.org/abs/quant-ph/9605043)
---

Page: https://redacted.gg/glossary/grovers-algorithm/