Computer Science/Discrete Mathematics Seminar II
No Exponential Quantum Speedup for SIS^inf Anymore
Given linear equations over a finite field and under infinity norm, the Short-Integer-Solution (SIS^inf) problem asks to find a solution where each entry is a small number.
In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the SIS^inf problem when the number of variables, equations, and field size satisfy certain trade-offs. This parameter regime is outside the normal range of cryptographic interest, but still with no known efficient classical algorithm. Their result was particularly exciting since SIS^inf 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 the SIS^inf problem and (more general) Constrained-Integer-Solution problems studied in their paper, showing there is no exponential quantum speedup anymore.
Joint work with Robin Kothari and Ryan O'Donnell.