Paper 2015/971

Attacks on the Search-RLWE problem with small error

Hao Chen, Kristin E. Lauter, and Katherine E. Stange

Abstract

The Ring Learning-With-Errors (RLWE) problem shows great promise for post-quantum cryptography and homomorphic encryption. We describe a new attack on the non-dual search RLWE problem with small error widths, using ring homomorphisms to finite fields and the chi-squared statistical test. In particular, we identify a ``subfield vulnerability'' (Section 5.2) and give a new attack which finds this vulnerability by mapping to a finite field extension and detecting non-uniformity with respect to the number of elements in the subfield. We use this attack to give examples of vulnerable RLWE instances in Galois number fields. We also extend the well-known search-to-decision reduction result to Galois fields with any unramified prime modulus $q$, regardless of the residue degree $f$ of $q$, and we use this in our attacks. The time complexity of our attack is $O(n q^{2f})$, where $n$ is the degree of $K$ and $f$ is the {\it residue degree} of $q$ in $K$. We also show an attack on the non-dual (resp. dual) RLWE problem with narrow error distributions in prime cyclotomic rings when the modulus is a ramified prime (resp. any integer). We demonstrate the attacks in practice by finding many vulnerable instances and successfully attacking them. We include the code for all attacks.

Note: Revised version corresponding to updates made for final publication.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. SIAM Journal on Applied Algebra and Geometry (SIAGA)
Keywords
attacksRLWEcryptanalysis
Contact author(s)
klauter @ microsoft com
History
2017-10-09: last of 2 revisions
2015-10-09: received
See all versions
Short URL
https://ia.cr/2015/971
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/971,
      author = {Hao Chen and Kristin E.  Lauter and Katherine E.  Stange},
      title = {Attacks on the Search-RLWE problem with small error},
      howpublished = {Cryptology ePrint Archive, Paper 2015/971},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/971}},
      url = {https://eprint.iacr.org/2015/971}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.