No Exponential Quantum Speedup for SIS∞ Anymore

In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the averagecase ℓ ∞ -Short Integer Solution (SIS ∞ ) problem, in a parameter range outside the normal range of cryptographic interest, but still with no known efficient classical algorithm. This was particularly exciting since SIS ∞ is a simple problem without structure, and their algorithmic techniques were different from those used in prior exponential quantum speedups.

We present efficient classical algorithms for all of the SIS ∞ and (more general) Constrained Integer Solution problems studied in their paper, showing there is no exponential quantum speedup anymore.