Paper 2018/494

Order-LWE and the Hardness of Ring-LWE with Entropic Secrets

Madalina Bolboceanu, Zvika Brakerski, Renen Perlman, and Devika Sharma

Abstract

We propose a generalization of the celebrated Ring Learning with Errors (RLWE) problem (Lyubashevsky, Peikert and Regev, Eurocrypt 2010, Eurocrypt 2013), wherein the ambient ring is not the ring of integers of a number field, but rather an *order* (a full rank subring). We show that our Order-LWE problem enjoys worst-case hardness with respect to short-vector problems in invertible-ideal lattices *of the order*. The definition allows us to provide a new analysis for the hardness of the abundantly used Polynomial-LWE (PLWE) problem (Stehlë et al., Asiacrypt 2009), different from the one recently proposed by Rosca, Stehlë and Wallet (Eurocrypt 2018). This suggests that Order-LWE may be used to analyze and possibly *design* useful relaxations of RLWE. We show that Order-LWE can naturally be harnessed to prove security for RLWE instances where the ``RLWE secret'' (which often corresponds to the secret-key of a cryptosystem) is not sampled uniformly as required for RLWE hardness. We start by showing worst-case hardness even if the secret is sampled from a subring of the sample space. Then, we study the case where the secret is sampled from an *ideal* of the sample space or a coset thereof (equivalently, some of its CRT coordinates are fixed or leaked). In the latter, we show an interesting threshold phenomenon where the amount of RLWE *noise* determines whether the problem is tractable. Lastly, we address the long standing question of whether high-entropy secret is sufficient for RLWE to be intractable. Our result on sampling from ideals shows that simply requiring high entropy is insufficient. We therefore propose a broad class of distributions where we conjecture that hardness should hold, and provide evidence via reduction to a concrete lattice problem.