Welcome to the resource topic for 2023/1839
Title:
Ring-LWE Hardness Based on Ideals of Hidden Orders of Number Fields
Authors: Charanjit S Jutla, Chengyu Lin
Abstract:We extend the known pseudorandomness of Ring-LWE to be based on lattices that do not correspond to any ideal of any order in the underlying number field. 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.
In this work we show that hardness of q-Ring-LWE can be based on worst-case hardness of ideal lattices in arbitrary orders O, as long as the order O satisfies the property that \frac{1}{m}\cdot O contains the ring of integers, for some m co-prime to q. Further, the hard lattice problems need not be given the order O itself as input. The reduction requires that the noise be a factor m more than the original Ring-LWE reduction. We also show that for the power-of-two cyclotomic number fields, there exist orders with m=4 such that non-trivial ideals of the order, which are not contained in the conductor, are non-invertible.
Another reduction shows that hardness of q-Ring-LWE can be based on worst-case hardness of lattices that correspond to sum of ideal-lattices in arbitrary and different orders in the number field, as long as the (set of) orders \{O_i\} satisfy the property that \frac{1}{m}\cdot O_i contains the ring of integers, for some m co-prime to q. We also show that for the power-of-two cyclotomic number fields, there exist orders O_1, O_2 with m=8 such that there are ideals I_1, I_2 of O_1, O_2 resp. with I_1+ I_2 not an ideal of any order in the number field.
ePrint: https://eprint.iacr.org/2023/1839
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .