On Algebraic Embedding for Unstructured Lattices

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\u27\u27 and in particular irrelevant for cryptographic applications. We then discuss the ability to embed unstructured lattices in ``friendlier\u27\u27 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