Paper 2022/1631

Enhancing Ring-LWE Hardness using Dedekind Index Theorem

Abstract

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. To mitigate this issue, Bolboceanu et al (Asiacrypt 2019) defined q-Order-LWE over any order (modulo q) in a number field and based its hardness on worst-case hard problems of ideal lattices of the same order, but restricted to invertible ideals. Orders generalize the ring of integers to non-Dedekind domains. In a subsequent work in 2021, they proved a non-effective ``ideal-clearing" lemma for q-Order-LWE for any q that is co-prime to index of the order in the ring of integers. This work can be shown to give an efficient reduction from any ideal of the same order. However, this requires factorization of arbitrary integers, namely the norm of the given ideal. In this work we give a novel approach to proving the ``ideal-clearing" lemma for q-Order-LWE by showing that all ideals I of an order are principal modulo qI, for any q that is co-prime to index of the order in the ring of integers. Further, we give a rather simple (classical) randomized algorithm to find a generator for this principal ideal, which makes our hardness reduction (from all ideals of the order) not require any further quantum steps on top of the quantum Gaussian sampling of the original Regev reduction. This also removes the ``known factorization" requirement on q for the original RLWE hardness result of Peikert et al. Finally, we recommend a ``twisted'' cyclotomic field as an alternative for the cyclotomic field used in NIST PQC algorithm CRYSTALS-Kyber, as it leads to a more efficient implementation and is based on hardness of ideals in a non-Dedekind domain following Dedekind index theorem.

Note: Jun 6, 2023 Update: Now the reduction works for all orders of a number field, including the ring of integers, polynomial ring and other non-maximal orders. The fast randomized algorithm to find the principal ideal generator (mod q) also works for all orders. We also recommend a non-Galois number field for PQC that is more efficient and potentially more secure than KYBER. Fixed minor typos. Added hyperlinks. Update on Dec 31, 2022: 1. Added references to M. Bolboceanu, Z. Brakerski, and D. Sharma 2021, that show a non-effective version of the clearing lemma for polynomial rings. With some work, their result can be extended to give a quantum efficient "clearing lemma". In contrast, our work gives a classically efficient clearing lemma. 2. We also give citation to Peiker-Pepin 2019. 3. Added a detailed technical overview subsection in the Introduction. 4. Added an appendix that gives an introduction to Dedekind Domains, even though our result's one aim is not to use Dedekind domains.