Paper 2020/440 Original: eprint.iacr.org/2020/440 ↗

Sublattice Attack on Poly-LWE with Wide Error Distributions

Abstract

The fundamental problem in lattice-based cryptography is the hardness of the Ring-LWE, which has been based on the conjectured hardness of approximating ideal-SIVP or ideal-SVP. Though it is now widely conjectured both are hard in classical and quantum computation model” there is no sufficient attacks proposed and considered. In this paper we propose the subset quadruple attack on general structured LWE problems over any ring endowed with a positive definite inner product and an error distribution. Hence from the view of subset quadruple attacks, the error distributions of feasible non-negligible subset quadruples should be calculated to test the hardness. Sublattice pair with an ideal attack is a special case of subset quadruple attack. A lower bound for the Gaussian error distribution is proved to construct suitable feasible non-negligible sublattices. From the sublattice pair with an ideal attack we prove that the decision Poly-LWE over ${\bf Z}[x]/(x^n-p_n)$ with certain special inner products and arbitrary polynomially bounded widths of Gaussian error distributions can be solved with the polynomial time for the sufficiently large polynomially bounded modulus parameters $p_n$.\\ Keywords: Poly-LWE, Ring-LWE, Wide Error distribution, Subset quadruple attack, Sublattice pair with an ideal.