S|LWE> is a quantum variant of LWE where the error term is encoded in the amplitude of a quantum state. The S|LWE> problem was originally studied by Chen, Liu, Zhandry [Eurocrypt 2022], motivated by solving a variant of SIS problem. In this talk I will talk about the previous result by Chen, Liu, Zhandry, as well as a recent paper on the hardness and algorithms for S|LWE> with Gaussian and other amplitudes. Our main results in the recent paper are 1. There exist quantum reductions from standard LWE or worst-case GapSVP to S|LWE> with Gaussian amplitude with unknown phase, and arbitrarily many samples. 2. There is a subexponential time algorithm for with Gaussian amplitude with known phase, given subexponentially many quantum samples. The algorithm is modified from Kuperberg's sieve, and in fact works for more general amplitudes as long as the amplitudes and phases are completely known. One way of interpreting our new result is: to show a sub-exponential time quantum algorithm for standard LWE, all we need is to handle phases in amplitudes better, either in the algorithm or the reduction. Based on two papers, one with Qipeng Liu, Mark Zhandry (eprint: https://eprint.iacr.org/2021/1093), and another with Zihan Hu, Qipeng Liu, Han Luo, Yaxin Tu (eprint https://eprint.iacr.org/2023/1498).
Yilei is an assistant professor at Tsinghua University Institute for Interdisciplinary Information Science (IIIS). Yilei's main research interests are lattice-based cryptography and quantum computation.