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://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://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
