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 <d...@cr.yp.to> Date: Friday, 29 August 2025 at 19:47 To: tls@ietf.org <tls@ietf.org> 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 -- tls@ietf.org To unsubscribe send an email to tls-le...@ietf.org
_______________________________________________ TLS mailing list -- tls@ietf.org To unsubscribe send an email to tls-le...@ietf.org
