Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Lattice cryptography, Ring-LWE

Date: received 16 Apr 2020, last revised 4 Jun 2020

Contact author: haochen at jnu edu cn,chenhao@fudan edu cn

Available format(s): PDF | BibTeX Citation

Version: 20200604:073521 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]