flâneur

Shtetl-Optimized » Blog Archive » That IACR preprint

scottaaronson.blog · 8,283 words · saved by 1 readers

For those who don’t yet know from their other social media: a week ago the cryptographer Yilei Chen posted a preprint, eprint.iacr.org/2024/555, claiming to give a polynomial-time quantum algorithm to solve lattice problems. For example, it claims to solve the GapSVP problem, which asks to approximate the length of the shortest nonzero vector in a given n-dimensional lattice, to within an approximation ratio of ~n4.5. The best approximation ratio previously known to be achievable in classical or quantum polynomial time was exponential in n. If it’s correct, this is an extremely big deal. It doesn’t quite break the main lattice-based cryptosystems, but it would put those cryptosystems into a precarious position, vulnerable to a mere further polynomial improvement in the approximation factor. And, as we learned from the recent NIST competition, if the lattice-based and LWE-based systems were to fall, then we really don’t have many great candidates left for post-quantum public-key cryptog

Shtetl-Optimized >> Blog Archive >> That IACR preprint Shtetl-Optimized The Blog of Scott Aaronson If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel. Also, please read Zvi Mowshowitz's masterpiece on how to fix K-12 education! --> << Avi Wigderson wins Turing Award! My Passover press release >> That IACR preprint Update (April 19): Apparently a bug has been found, and the author has withdrawn the claim (see the comments). For those who don&#8217;t yet know from their other social media: a week ago the cryptog

related reading