CryptoDB
Quantum Algorithms for Variants of AverageCase Lattice Problems via Filtering
Authors: 


Download:  
Conference:  EUROCRYPT 2022 
Abstract:  We show polynomialtime quantum algorithms for the following problems: (*) 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. (*) Extrapolated dihedral coset problem (EDCP) with certain parameters. (*) Learning with errors (LWE) problem given LWElike quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions. We show polynomialtime quantum algorithms for the following problems: (*) 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. (*) Learning with errors (LWE) problem given LWElike quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions. (*) 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 worstcase lattice problems. Still, no classical or quantum polynomialtime 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 LWElike quantum states. Our main contribution is solving LWE given LWElike quantum states with interesting parameters using a filtering technique. We show polynomialtime quantum algorithms for the following problems: (*) 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. (*) Learning with errors (LWE) problem given LWElike quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions. (*) 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 worstcase lattice problems. Still, no classical or quantum polynomialtime 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 LWElike quantum states. Our main contribution is solving LWE given LWElike quantum states with interesting parameters using a filtering technique. 
Video from EUROCRYPT 2022
BibTeX
@inproceedings{eurocrypt202231847, title={Quantum Algorithms for Variants of AverageCase Lattice Problems via Filtering}, publisher={SpringerVerlag}, author={Yilei Chen and Qipeng Liu and Mark Zhandry}, year=2022 }