[TLS] Re: Concerns about the current draft.

[John Mattsson <[e-mail]>]

Sophie Schmieg wrote:
> As Bas mentioned, there is currently no indication that Grover's algorithm can practically break AES-128 any time soon.
Completely agree.

>Grover's algorithm is inherently sequential, and cannot be parallelized,
Cannot be _effectively_ parallelized would be a more theoretically correct statement. But practically, Grover’s algorithm will never be used for breaking AES-128. Quantum computers will also remain much slower and much more expensive than classical computers. Anybody claiming Grover's algorithm is a threat to any cryptography should provide detailed calculation of the cost, size, and time. With realistic assumptions you end up with result like “a huge cluster of one billion CRQCs (according to one estimate costing one billion USD each) would take a million years of uninterrupted calculation to find a single AES-128 key” or “require qubits covering the surface area of the Moon”.

https://datatracker.ietf.org/liaison/1942/
https://www.youtube.com/watch?v=eB4po9Br1YY&t=3227s

John

From: D. J. Bernstein <[e-mail]>
Date: Friday, 29 August 2025 at 19:47
To: [e-mail] <[e-mail]>
Subject: [TLS] Re: Concerns about the current draft.
Sophie Schmieg writes:
> Grover's algorithm is inherently sequential, and cannot be
> parallelized, making the standard approach of throwing more compute at
> the problem to scale up infeasible.

One can split the search space across many parallel quantum processors
and run a smaller Grover search on each part of the space, as noted in,
e.g., https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Farxiv.org%2Fabs%2Fquant-ph%2F0309123&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7Ce91ec897b40744e464bc08dde72429dd%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638920864700657440%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=haVw1vVYALl5qAbq7VJPRciy2fAjPgrA0NEuAVbxyiY%3D&reserved=0<https://arxiv.org/abs/quant-ph/0309123> from Grover and Rudolph.

To some extent it's possible to combine this with multi-target attacks.
See https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fcr.yp.to%2Fpapers.html%23groverrho&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7Ce91ec897b40744e464bc08dde72429dd%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638920864700717818%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=CK8nBl6TfEM5LwY%2Fznl7KgJjT0x4dNiUG4IeSL7xf4s%3D&reserved=0<https://cr.yp.to/papers.html#groverrho>.

Even without quantum computers, 2^40-target attacks against AES-128 are
already a feasible computation today for large-scale attackers. One can
try to stop these attacks by having every AES-128 application randomize
every input block, but we keep seeing people screw this up. This is the
sort of thing that _probably_ ends up working for TLS, but it's fragile,
and the broader habit of tolerating this sort of fragility is certainly
a big factor in the problems that we _have_ seen in TLS.

I agree that the Grover speedup compared to non-quantum searches comes
from the number of serial iterations carried out on each processor, and
meanwhile this has to fight against the quantum-computation overhead---
which could end up as 2^30 or 2^40; we don't know yet. But this doesn't
makes AES-128 a safe option: on the contrary, tolerating AES-128 will
end up compromising the confidentiality of some user data.

> confirmed the infeasibility of Grover's in at least the
> medium term of several decades to centuries

I see no basis for this claim.

> the reason for ECC + lattice based hybrids are becoming less
> compelling with every day that passes in which lattices do not get
> broken

One of the talks at Crypto 2025 last week said that none of the Kyber
parameters meet their claimed security levels.

---D. J. Bernstein

_______________________________________________
TLS mailing list -- [e-mail]
To unsubscribe send an email to [e-mail]