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 computational number theory. In our previous paper we presented a general theory of subset attack on the Ring-LWE with not only the Gaussian error distribution but also general error distributions. By the usage of our subset attack from sublattice quadruples we prove that the decision Ring-LWE (then the search version) over two-to-power cyclotomic integer rings with certain sufficiently large 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 the quantum polynomial time. Therefore post-quantum 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.

Note: No polynomially bounded index ideal used in number field case.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Ring-LWEWidthSubset attackSublattice quadruple
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
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/418,
      author = {Hao Chen},
      title = {Ring-LWE over two-to-power cyclotomics is not hard},
      howpublished = {Cryptology ePrint Archive, Paper 2021/418},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/418}},
      url = {https://eprint.iacr.org/2021/418}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.