Paper 2020/440

Sublattice Attacks on Ring-LWE with Wide Error Distributions I

Hao Chen

Abstract

Since 2010 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 ideal-SIVP 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 of degrees going to the infinity, such that the decision Ring-LWE with very wide error distributions over integer rings of can be solved by a polynomial time algorithm from our sublattice attack. The widths of error distributions in our attack is in the range of hardness reduction results. Hence we also prove that approximating ideal-SIVP with some polynomial factor for ideal lattices in these number fields can be solved by a polynomial time quantum algorithm.