International Association
for Cryptologic Research

In this work we extend the known pseudorandomness of Ring-LWE (RLWE) to be based on ideal lattices of non Dedekind domains. In earlier works of Lyubashevsky et al (EUROCRYPT 2010) and Peikert et al (STOC 2017), the hardness of RLWE was based on ideal lattices of ring of integers of number fields, which are known to be Dedekind domains. While these works extended Regev's (STOC 2005) quantum polynomial-time reduction for LWE, thus allowing more efficient and more structured cryptosystems, the additional algebraic structure of ideals of Dedekind domains leaves open the possibility that such ideal lattices are not as hard as general lattices.

We now show that for any number field $\mathbb{Q}[X]/(f(X))$, for all prime integers $p$ such that the factorization of $f(X)$ modulo $p$ passes the Dedekind index theorem criterion, which is almost all $p$, we can base $p$-power RLWE in the polynomial ring $\mathbb{Z}[X]/(f(X))$ itself and its hardness on hardness of ideal lattices of this ring. This ring can potentially be a strict sub-ring of the ring of integers of the field, and hence not be a Dedekind domain. We also give natural examples, and prove that certain ideals require at least three generators, as opposed to two sufficient for Dedekind domains. Such rings also do not satisfy many other algebraic properties of Dedekind domains such as ideal invertibility. Our proof technique is novel as it builds an algebraic theory for general such rings that also include cyclotomic rings.