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 algorithmRelated terms
- Shor's algorithm — A quantum algorithm, published by Peter Shor in 1994, that could factor large numbers and solve discrete logarithms quickly on a big enough quantum computer.
- quantum computer — A computer that uses the physics of quantum states to solve certain kinds of mathematical problems far faster than ordinary computers can.
- AES — The Advanced Encryption Standard: the widely used symmetric encryption algorithm standardised by NIST.
- key length — The size of a cryptographic key in bits, which sets how many possible keys an attacker would have to try.
Taught in
- Post-Quantum Cryptography & Key Lifecycles — Cybersecurity Fundamentals, GRC & Cryptography