Contrary to popular superstition, AES 128 is just fine in a post-quantum world

Source: Ars Technica

Overview

On Monday Filippo Valsorda finally channeled years of frustration over the widely held misunderstanding into a blog post titled Quantum Computers Are Not a Threat to 128‑bit Symmetric Keys.

“There’s a common misconception that quantum computers will ‘halve’ the security of symmetric keys, requiring 256‑bit keys for 128 bits of security. That is not an accurate interpretation of the speedup offered by quantum algorithms, it’s not reflected in any compliance mandate, and risks diverting energy and attention from actually necessary post‑quantum transition work.” – Filippo Valsorda

Misconception about quantum security

The easy part of the argument is the statement above. The much harder part is the math and physics that explains why the misconception is wrong.

Classical vs. quantum brute‑force search

Classical parallelization

Classical computers can perform multiple searches simultaneously. This capability lets large tasks be broken into smaller pieces that run in parallel, completing the overall job faster.

Grover’s algorithm and parallelization

Grover’s algorithm, by contrast, requires a long‑running serial computation where each search is done one at a time. As Valsorda explained in an interview:

“What makes Grover special is that as you parallelize it, its advantage over non‑quantum algorithms gets smaller.”

Example with a small key space

• Suppose there are 256 possible combinations to a lock.
• A normal (classical) attack would take 256 tries.
• If you enlist three friends, each does 64 tries → 256 / 4 = 64 tries per person. This is classical parallelization.

With Grover’s algorithm:

• In theory you could do √256 = 16 tries sequentially.
• If you again ask three friends for help, each must do √256 / 4 = 8 tries.
• Total work: 8 × 4 = 32 tries, which is more than the 16 you would have done alone. Asking for help to parallelize the attack actually makes it slower—something that never happens with classical attacks.

Impact on AES‑128 security

In realistic scenarios the key space is astronomically larger. If we impose a reasonable constraint on the attacker (e.g., the attack must finish within 10 years), the total work required becomes far greater than 2⁶⁴. Moreover, the naïve 2⁶⁴ figure assumes you could treat AES as a single operation on a single qubit, which is not the case.

Combining these observations pushes the effective cost of a Grover‑based attack on AES‑128 to roughly 2¹⁰⁴ operations (give or take), well beyond any practical security threshold.

Expert commentary

Sophie Schmieg, a senior cryptography engineer at Google, summarized the situation:

[Insert Sophie Schmieg’s quoted explanation here if available]

The consensus among experts is that AES‑128 remains secure against foreseeable quantum attacks, and the push for 256‑bit symmetric keys solely due to quantum concerns is unnecessary.