Paper 2018/494

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

Zvika Brakerski and Renen Perlman

Abstract

The Ring Learning with Errors problem (RLWE) introduced by Lyubashevsky, Peikert and Regev (LPR, Eurocrypt 2010, Eurocrypt 2013) quickly became a central element in cryptographic literature and a foundation to numerous cryptosystems. RLWE is an average case problem whose hardness is provably related to the worst case hardness of ideal lattice problems. However, in many cases optimizations and other considerations necessitate generating RLWE instances from distributions for which the worst case reduction does not apply, thus leaving the resulting cryptosystem secure only by heuristic reasons. The focus of this work is RLWE with non-uniform distribution on secrets. A legal RLWE secret is (roughly) a uniform element in the ring of integers of a number field, modulo an integer $q$. We consider two main classes of "illegal" distributions of secrets. The first is sampling from a subring of the intended domain. We show that this translates to a generalized form of RLWE that we call Order-LWE, we provide worst case hardness results for this new problem, and map out regimes where it is secure and where it is insecure. Two interesting corollaries are a (generalization of) the known hardness of RLWE with secrets sampled from the ring of integers of a subfield, and a new hardness results for the Polynomial-LWE (PLWE) problem, with different parameters than previously known. The second is sampling from a $k$-wise independent distribution over the CRT representation of the secret. We cannot show worst case hardness in this case, but instead present a single average case problem (specifically, bounded distance decoding on a fixed specific distribution over lattices) whose hardness implies the hardness of RLWE for all such distributions of secrets.