TY - GEN

T1 - Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering

AU - Chen, Yilei

AU - Liu, Qipeng

AU - Zhandry, Mark

N1 - Funding Information:
Acknowledgement. We sincerely thank Gábor Ivanyos for telling us the results in [IPS18]. We would also like to thank Luowen Qian, Léo Ducas, and the anonymous reviewers for their helpful comments. Y.C. is supported by Tsinghua University start-up funding and Shanghai Qi Zhi Institute. Q.L. is supported by the Simons Institute for the Theory of Computing, through a Quantum Postdoctoral Fellowship. M.Z. is supported in part by NSF.
Publisher Copyright:
© 2022, International Association for Cryptologic Research.

PY - 2022

Y1 - 2022

N2 - We show polynomial-time quantum algorithms for the following problems: 1.Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a constant.2.Learning with errors (LWE) problem given LWE-like quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions.3.Extrapolated dihedral coset problem (EDCP) with certain parameters. The SIS, LWE, and EDCP problems in their standard forms are as hard as solving lattice problems in the worst case. However, the variants that we can solve are not in the parameter regimes known to be as hard as solving worst-case lattice problems. Still, no classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider. For EDCP, our quantum algorithm slightly extends the result of Ivanyos et al. (2018). Our algorithms for variants of SIS and EDCP use the existing quantum reductions from those problems to LWE, or more precisely, to the problem of solving LWE given LWE-like quantum states. Our main contribution is solving LWE given LWE-like quantum states with interesting parameters using a filtering technique.

AB - We show polynomial-time quantum algorithms for the following problems: 1.Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a constant.2.Learning with errors (LWE) problem given LWE-like quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions.3.Extrapolated dihedral coset problem (EDCP) with certain parameters. The SIS, LWE, and EDCP problems in their standard forms are as hard as solving lattice problems in the worst case. However, the variants that we can solve are not in the parameter regimes known to be as hard as solving worst-case lattice problems. Still, no classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider. For EDCP, our quantum algorithm slightly extends the result of Ivanyos et al. (2018). Our algorithms for variants of SIS and EDCP use the existing quantum reductions from those problems to LWE, or more precisely, to the problem of solving LWE given LWE-like quantum states. Our main contribution is solving LWE given LWE-like quantum states with interesting parameters using a filtering technique.

UR - http://www.scopus.com/inward/record.url?scp=85132120990&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85132120990&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-07082-2_14

DO - 10.1007/978-3-031-07082-2_14

M3 - Conference contribution

AN - SCOPUS:85132120990

SN - 9783031070815

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 372

EP - 401

BT - Advances in Cryptology – EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2022, Proceedings

A2 - Dunkelman, Orr

A2 - Dziembowski, Stefan

PB - Springer Science and Business Media Deutschland GmbH

T2 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022

Y2 - 30 May 2022 through 3 June 2022

ER -