(AGENPARL) – WORLD WIDE, lun 18 gennaio 2021
ePrint Report: On Algebraic Embedding for Unstructured Lattices
Madalina Bolboceanu, Zvika Brakerski, Devika Sharma
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.