Paper 2018/494

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

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


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.

Available format(s)
Publication info
A major revision of an IACR publication in ASIACRYPT 2019
Contact author(s)
renen perlman @ weizmann ac il
2019-09-04: last of 2 revisions
2018-05-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Madalina Bolboceanu and Zvika Brakerski and Renen Perlman and Devika Sharma},
      title = {Order-LWE and the Hardness of Ring-LWE with Entropic Secrets},
      howpublished = {Cryptology ePrint Archive, Paper 2018/494},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.