ECCC-Report TR21-126https://eccc.weizmann.ac.il/report/2021/126Comments and Revisions published for TR21-126en-usWed, 06 Oct 2021 06:42:24 +0300
Revision 1
| Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering |
Qipeng Liu,
Yilei Chen,
Mark Zhandry
https://eccc.weizmann.ac.il/report/2021/126#revision1We show polynomial-time 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 LWE-like quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions.
The SIS, EDCP, and LWE 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 those variants.
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 contributions are introducing a filtering technique and solving LWE given LWE-like quantum states with interesting parameters.Wed, 06 Oct 2021 06:42:24 +0300https://eccc.weizmann.ac.il/report/2021/126#revision1
Paper TR21-126
| Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering |
Qipeng Liu,
Yilei Chen,
Mark Zhandry
https://eccc.weizmann.ac.il/report/2021/126We show polynomial-time 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 LWE-like quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions.
The SIS, EDCP, and LWE 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 those variants.
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 contributions are introducing a filtering technique and solving LWE given LWE-like quantum states with interesting parameters.Sun, 29 Aug 2021 10:01:12 +0300https://eccc.weizmann.ac.il/report/2021/126