Grover's algorithm

A quantum search algorithm that could find a secret key in roughly the square root of the number of tries an ordinary search needs.

In more detail

Against symmetric ciphers and hashes this roughly halves the effective strength in bits, so a 128-bit key would behave more like a 64-bit one against a quantum attacker. Doubling the key length restores the margin, which is why AES-256 is considered safe. In practice the speed-up is even smaller, because the steps must run one after another and cannot be split across many machines efficiently.

Example

AES-256 keeps about 128 bits of security against Grover's algorithm

Related terms

Taught in

References