True or false: "Quantum computers represent the strongest possible attack against block ciphers."
False — the classical Merkle-Hellman TMTO ($k^{1/3}$) is actually stronger than quantum brute force (Grover's algorithm at $k^{1/2}$) against block ciphers.
Comparison for a 128-bit block cipher:
| Attack | Effective Security |
|---|---|
| Classical brute force | $2^{128}$ |
| Grover (quantum) | $2^{64}$ (= $k^{1/2}$) |
| Merkle-Hellman TMTO ($k^{2/3}$) | $2^{85}$ |
| Merkle-Hellman TMTO ($k^{1/3}$) | $2^{43}$ ← strongest! |
The surprising result: The theoretical classical TMTO at $k^{1/3}$ reduces 128-bit security to just 43 bits — far worse than Grover's 64 bits. Quantum computing is not the worst-case scenario for block ciphers.
However, there's a catch: The $k^{1/3}$ bound is theoretical — no practical construction achieves it for all cases. The realistic $k^{2/3}$ TMTO gives $2^{85}$ security, which is worse than Grover. So in practice, quantum attacks currently appear stronger.
For asymmetric crypto, the story is completely different — Shor's algorithm breaks RSA/DH/ECC in polynomial time, which is far more devastating than any TMTO on block ciphers.
Go deeper:
Grover's algorithm (Wikipedia) — the quantum bound that theoretical TMTO can still beat.