Cryptology ePrint Archive: Report 2019/791

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? 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 5 Dec 2019

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

Available format(s): PDF | BibTeX Citation

Note: Corrected version

Version: 20191205:233042 (All versions of this report)

Short URL: ia.cr/2019/791


[ Cryptology ePrint archive ]