You are looking at a specific version 20151009:210943 of this paper. See the latest version.

Paper 2015/971

Attacks on Search RLWE

Hao Chen, Kristin Lauter, and Katherine E. Stange

Abstract

We describe a new attack on the Search Ring Learning-With-Errors (RLWE) problem based on the chi-square statistical test, and give examples of RLWE instances in Galois number fields which are vulnerable to our attack. We prove a search-to-decision reduction for Galois fields which applies for 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(q^{2f})$, where $f$ is the {\it residue degree} of $q$ in $K$. We also show an attack on the RLWE problem in general cyclotomic rings (non $2$-power cyclotomic rings) which works when the modulus is a ramified prime. We demonstrate the attacks in practice by finding many vulnerable instances and successfully attacking them. We include the code for all attacks.

Note: Under submission elsewhere.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
RLWEAttacksCryptanalysis
Contact author(s)
chenh123 @ uw edu
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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.