Paper 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? 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.

Note: Corrected version

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Ring-LWEOrder LWELWE over a number field lattice
Contact author(s)
haochen @ jnu edu cn
chenhao @ fudan edu cn
History
2019-12-17: last of 9 revisions
2019-07-14: received
See all versions
Short URL
https://ia.cr/2019/791
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/791,
      author = {Hao Chen},
      title = {Sublattice Attacks on LWE over Arbitrary Number Field Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2019/791},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/791}},
      url = {https://eprint.iacr.org/2019/791}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.