Paper 2021/053

On Algebraic Embedding for Unstructured Lattices

Madalina Bolboceanu, Bitdefender, Romania
Zvika Brakerski, Weizmann Institute of Science, Israel
Devika Sharma, Weizmann Institute of Science, Israel
Abstract

Lattice-based cryptography, the study of cryptographic primitives whose security is based on the hardness of so-called lattice problems, has taken center stage in cryptographic research in recent years. It potentially offers favorable security features, even against quantum algorithms. One of the main obstacles for wide adoption of this type of cryptography is its unsatisfactory efficiency. To address this point, efficient lattice-based cryptography usually relies on the intractability of problems on lattices with additional algebraic structure (such as so-called ideal-lattices or module-lattices). It is an important open question to evaluate the hardness of such lattice problems, and their relation to the hardness of problems on unstructured lattices. It is a known fact that an unstructured lattice, which is simply an additive discrete group in Euclidean space, can be cast as an ideal-lattice in some \emph{order} of a number field (and thus, in a rather trivial sense, that ideals in orders are as general as unstructured lattices). However, it is not known whether this connection can be used to imply useful hardness results for structured lattices, or alternatively new algorithmic techniques for unstructured lattices. In this work we establish a gradient of hardness for the Order-LWE problem (a generalization of the well known Ring-LWE problem), as it varies over orders in a number field. Furthermore, we show that, in every number field, there are certain orders such that the corresponding Order-LWE problem is at least as hard as the (unstructured) LWE problem. So in general one should not hope to solve (any) Order-LWE more efficiently than LWE. However, we show that this connection holds in orders that are very ``skewed'' and hence, perhaps, irrelevant for improving efficiency in cryptographic applications. We further improve the hardness result for Order-LWE, to include \textit{all} ideal lattices, closing a gap left in prior work. This establishes a direct connection between problems on unstructured lattices and the structured problem of Order-LWE.

Note: Revised version: changes made after manuscript got accepted in PKC 2024.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in PKC 2024
Keywords
LWEOrder-LWElatticesnumber fields
Contact author(s)
madalinabolboceanu @ gmail com
zvika brakerski @ weizmann ac il
devika sharma @ weizmann ac il
History
2024-01-21: last of 2 revisions
2021-01-18: received
See all versions
Short URL
https://ia.cr/2021/053
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/053,
      author = {Madalina Bolboceanu and Zvika Brakerski and Devika Sharma},
      title = {On Algebraic Embedding for Unstructured Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2021/053},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/053}},
      url = {https://eprint.iacr.org/2021/053}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.