Sublattice Attacks on Ring-LWE with Wide Error Distributions I
Since the Lyubashevsky-Peikert-Regev Eurocrypt 2010 paper the Ring-LWE has been the hard computational problem for lattice cryptographic constructions. The fundamental problem is its hardness which has been based on the conjectured hardness of approximating idealSIVP or ideal-SVP. Though it is now widely conjectured both are hard in classical and quantum computation model there have no sufficient attacks proposed and considered. In this paper we propose sublattice attacks on Ring-LWE over an arbitrary number field from sublattice pairs. We give a sequence of number fields Kn of degree dn −→ ∞, such that the decision Ring-LWE with very wide error distributions over integer rings of Kn can be solved by a polynomial (in dn) time algorithm from our sublattice attack. The widths of error distributions in our attack is in the range of Peikert-Regev-Stephens-Davidowitz hardness reduction results in their STOC 2017 paper. Hence we also prove that approximating ideal-SIV Ppoly(d) with some polynomial factor for ideal lattices in these number fields can be solved by a polynomial time quantum algorithm.