Cryptology ePrint Archive: Report 2018/494

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

Madalina Bolboceanu and Zvika Brakerski and 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.

Category / Keywords:

Original Publication (with major differences): IACR-ASIACRYPT-2019

Date: received 21 May 2018, last revised 4 Sep 2019

Contact author: renen perlman at weizmann ac il

Available format(s): PDF | BibTeX Citation

Version: 20190904:154611 (All versions of this report)

Short URL: ia.cr/2018/494


[ Cryptology ePrint archive ]