Cryptology ePrint Archive: Report 2021/053

On Algebraic Embedding for Unstructured Lattices

Madalina Bolboceanu and Zvika Brakerski and Devika Sharma

Abstract: Efficient lattice-based cryptography usually relies on the intractability of problems on lattices with algebraic structure such as 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 can be cast as an ideal-lattice in some 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 show that the Order-LWE problem (a generalization of the well known Ring-LWE problem) on certain orders is at least as hard as the (unstructured) LWE problem. So in general one should not hope to solve Order-LWE more efficiently than LWE. However, we only show that this connection holds in orders that are very ``skewed'' and in particular irrelevant for cryptographic applications. We then discuss the ability to embed unstructured lattices in ``friendlier'' orders, which requires devising an algorithm for computing the conductor of relevant orders. One of our technical tools is an improved hardness result for Order-LWE, closing a gap left in prior work.

Category / Keywords: foundations / LWE, Order-LWE, lattices, number fields

Date: received 14 Jan 2021, last revised 16 Apr 2021

Contact author: madalinabolboceanu at gmail com, zvika brakerski at weizmann ac il, devika sharma at weizmann ac il

Available format(s): PDF | BibTeX Citation

Note: Revised version: only structural changes made in section 5.

Version: 20210416:111359 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]