Applied Cryptography
Searching for the key of an n-bit symmetric-key cipher with Grover's algorithm on a quantum computer is said to take about 2^(n/2) computations. Using this simple guideline, which of the following is closest to the security of AES-128 against quantum computers?
- AAbout 64-bit security
- BAbout 127-bit security
- CAbout 128-bit security
Show answer and explanation
Answer: A. About 64-bit security
Grover's algorithm reduces the number of brute-force tries from 2ⁿ to about 2^(n/2), its square root. For AES-128 this is 2^(128/2) = 2⁶⁴ tries, so the security is about 64 bits. Unlike Shor's algorithm, which breaks public-key cryptography in polynomial time, this can be countered by using longer keys, and AES-256 retains about 128-bit security. However, Grover's algorithm benefits little from parallelization and must also run a long computation without errors, so this is only a simple guideline, and in NIST's evaluation of post-quantum cryptography, being as hard as a key search on AES-128 is the yardstick for the lowest security category.
- A. Correct. 2^(128/2) = 2⁶⁴, about 64-bit security.
- B. About 127 bits corresponds to classical brute force finding the key on average after half the tries, 2¹²⁷.
- C. This is the value assuming no effect at all from quantum computers. Grover's algorithm roughly halves the number of security bits.