**Sublattice Attacks on LWE over Arbitrary Number Field Lattices**

*Hao Chen*

**Abstract: **Learning with errors over algebraic integer rings (Ring-LWE) was
introduced by Lyubashevsky, Peikert and Regev in Eurocrypt 2010 and
has been served as the fundamental hard problem for lattice cryptogra-
phy. In recent years variants of algebraically structured learning with
errors such as order-LWE, module-LWE and LWE over number field
lattices have been introduced. In this paper we prove that for LWE
over a number field lattice L in an arbitrary number field of degree √
logn
n, when the width is smaller than O(λ1(L∨1 )) for some polynomially
bounded cardinality |L∨/L1| sublattice L1 ⊂ L∨ with non-negligible OL1 , then the LWE over L can be solved by a polynomial time al- gorithm for some modulus parameters. This leads to new sublattice bounds on widths of solvable Ring-LWE instances. From our sublat- tice attack on Ring-LWE it is natural to ask if there exists sublattices L ⊂ RK for some number field K with very small λ1(L∨) and non- negligible OL? In practice sub lattice attack is very necessary for Ring-LWE based lattice cryptography. Secondly we prove that for LWE over an arbitrary num- ber field lattice there are infinitely many modulus parameters such that the problem can be transformed to distinguishing the discretization of one-dimensional continuous Gaussian distribution from the uniform distribution. Hence for these modulus parameters these LWE over ar- bitrary number arbitrary number field lattices can be solved within a polynomial time for a suitable large width (though still narrower than the range in hardness reduction results). While for plain LWE there is no such modulus parameters.

**Category / Keywords: **foundations / Ring-LWE, Order LWE, LWE over a number field lattice, Width of the Gaussian of error distribution.

**Date: **received 7 Jul 2019, last revised 16 Dec 2019

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

**Available format(s): **PDF | BibTeX Citation

**Note: **Corrected version

**Version: **20191217:032152 (All versions of this report)

**Short URL: **ia.cr/2019/791

[ Cryptology ePrint archive ]