No exponential quantum speedup for ${\mathrm{SIS}}^{\infty }$ anymore

Abstract

In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case ${\ell }_{\infty }$-Short Integer Solution (${\mathrm{SIS}}^{\infty }$) 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 ${\mathrm{SIS}}^{\infty }$ 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 ${\mathrm{SIS}}^{\infty }$ and (more general) Constrained Integer Solution problems studied in their paper, showing there is no exponential quantum speedup anymore.