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

Yilei Chen, Qipeng Liu, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2022, Proceedings
EditorsOrr Dunkelman, Stefan Dziembowski
PublisherSpringer Science and Business Media Deutschland GmbH
Pages372-401
Number of pages30
ISBN (Print)9783031070815
DOIs
StatePublished - 2022
Event41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022 - Trondheim, Norway
Duration: May 30 2022Jun 3 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13277 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022
Country/TerritoryNorway
CityTrondheim
Period5/30/226/3/22

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering'. Together they form a unique fingerprint.

Cite this