Paper 2021/418
Ring-LWE over two-to-power cyclotomics is not hard
Hao Chen
Abstract
The Ring-LWE over two-to-power cyclotomic integer rings has been the hard computational problem for lattice cryptographic constructions. Its hardness and the conjectured hardness of approximating ideal SIVP for ideal lattices in two-to-power cyclotomic fields have been the fundamental open problems in lattice cryptography and the complexity theory of computational problems of ideal lattices. In this paper we present a general theory of sublattice attack on the Ring-LWE with not only the Gaussian error distribution but also general error distributions. By the usage of our sublattice attack we prove that the decision Ring-LWE over two-to-power cyclotomic integer rings with certain polynomially bounded modulus parameters when degrees d_n = 2^{n−1} going to the infinity can be solved by a polynomial (in d_n) time algorithm for wide error distributions with widths in the range of Peikert-Regev-Stephens-Davidowitz hardness reduction results in their STOC 2017 paper. Hence we also prove that approximating idealSIV Ppoly(dn) with some polynomial factors for ideal lattices in two-to-power cyclotomic fields can be solved within quantum polynomial time. Therefore the lattice cryptographic constructions can not be based on the ”hardness” of Ring-LWE over two-to-power cyclotomic integer rings even in the classical computational model.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Ring-LWETwo-to-power cyclotomicsSublattice attack
- Contact author(s)
- chenhao @ fudan edu cn,haochen @ jnu edu cn
- History
- 2021-05-22: last of 3 revisions
- 2021-03-30: received
- See all versions
- Short URL
- https://ia.cr/2021/418
- License
-
CC BY