We 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. (*) 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. (*) 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.
翻译:我们为下列问题展示了多元时量算法:(*) 在无限规范下,短期整数(SIS)问题(SIS)问题,因为公共矩阵非常广泛,模数是多元型的大质质,而无限规范的界限定在模数减去常数的一半。 (*) 学习有误(LWE)问题,因为LWE类量子国家存在多模式性大和某些差错分布,包括约束性统一分布和拉普尔分布。 (*) 具有某些参数的外推异差异差共合(EDCP)问题。SIS、LWE和EDCP问题的标准形式与解决最坏情况下的拉特类问题一样困难。然而,我们所能解决的变异性在已知的参数体系中并不难于解决最坏情况的问题。然而,我们所考虑的SIS和LWE的变异性(EWE) 和LWE的变异性(LWE) 。