For most lattice-based schemes (including Kyber/ML-KEM and Dilithium/ML-DSA), the best known attacks are generic lattice attacks, and the fastest generic lattice attacks are based on lattice sieving. However, lattice sieving is an extremely memory-intensive algorithm: how does this change the landscape of attack complexity?
In this talk I will argue that at the scale of hardware necessary to run these attacks, we must consider parallelism, and the most realistic parallel, planet-sized architecture is a vast mesh network. I will give a straightforward modification of existing lattice sieving algorithms that will run on this architecture, and then a more complicated recursive version that nearly matches the asymptotic cost obtained by ignoring all these real-world constraints. In fact, if we have a 3-dimensional mesh network (imagine filling the interior of the moon with computers), then we can match the unconstrained cost, but with a 2-dimensional network (imagine covering the surface of the moon with computers) accounting for memory and routing does increase the cost estimates. If we make some dubious assumptions about the constants, this adds about 14 bits to the security of Kyber-512.
Paper: https://cic.iacr.org/p/1/3/6
Sam Jaques is an assistant professor at the University of Waterloo, where he works on quantum cryptanalysis and generally considers attacks by computers that may never exist. He has a PhD from Oxford University and a master’s from the University of Waterloo.