Breakthrough Ends Belief in Exponential Quantum Speedup for SIS^inf Problems

In a recent seminar at the Institute for Advanced Study, Kewen Wu unveiled groundbreaking research that overturns a previously held cornerstone in quantum computation. The presentation, titled "No Exponential Quantum Speedup for SIS^inf Anymore," tackled the Short-Integer-Solution problem under the infinity norm (SIS^inf), long considered a candidate for exponential quantum speedup and vital to post-quantum cryptography assumptions.

The work builds on a 2021 result by Chen, Liu, and Zhandry, who identified an efficient quantum algorithm for a specific parameter regime of SIS^inf -until now unmatched by classical algorithms. Wu, collaborating with Robin Kothari and Ryan O’Donnell, demonstrated new classical algorithms that solve SIS^inf as efficiently as previously lauded quantum methods in these regimes.

The SIS^inf problem, crucial for cryptographic applications, essentially asks for vectors over a finite field whose coefficients are bounded in absolute value. Quantum algorithms previously showed advantage in regimes outside cryptographic norms, but these new classical algorithms close that gap for general and constrained integer solutions. This advancement prompts a reevaluation of quantum advantage in lattice-based cryptography and suggests a need to reassess the foundations of certain post-quantum cryptosystems.

Wu’s findings not only reshape expectations for quantum computing’s power but also reinforce the security premises of cryptosystems relying on the assumed difficulty of SIS^inf. The seminar drew attention from the computer science and cryptography communities, eager to explore the practical and theoretical implications of these new results.

Reference/Source:

Institute for Advanced Study Seminar: No Exponential Quantum Speedup for SIS^inf Anymore - Kewen Wu