Quiz Entry - updated: 2026.07.14
For a single block cipher, what is the realistic vs. optimistic TMTO effort, and why do they differ?
Realistic TMTO on a single block cipher costs $k^{2/3}$ each for time and storage (≈70% success probability). The optimistic/theoretical estimate is $k^{1/3}$ each, but this assumes ideal conditions.
Why two estimates exist:
- Realistic ($k^{2/3}$): Based on current best-known TMTO constructions (Merkle-Hellman). With $k^{2/3}$ effort in both time and storage, the attack succeeds with about 70% probability
- Optimistic ($k^{1/3}$): A theoretical lower bound — the minimum effort that any TMTO could potentially achieve. No practical construction reaches this yet for all cases
Example for AES-128 ($k = 2^{128}$):
| TMTO Type | Time | Storage |
|---|---|---|
| Realistic ($k^{2/3}$) | $2^{85} \approx 5 \times 10^{25}$ | $2^{90} \approx 10^{27}$ |
| Optimistic ($k^{1/3}$) | $2^{43} \approx 7 \times 10^{12}$ | $2^{45} \approx 10^{13}$ |
The practical takeaway: TMTO effectively reduces a cipher's security. A 128-bit key provides roughly 85-bit security against realistic TMTO — still safe, but far less than the nominal 128 bits. With the optimistic bound, it would drop to ~43 bits, which would be breakable.
Go deeper:
Key size (Wikipedia) — effective security levels once trade-offs are factored in.