@techreport{chen2015attacks,
author = {Chen, Hao and Lauter, Kristin and Stange, Katherine E},
title = {Attacks on search RLWE},
year = {2015},
month = {October},
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(q2f), 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.},
url = {http://approjects.co.za/?big=en-us/research/publication/attacks-on-search-rlwe/},
number = {MSR-TR-2015-93},
}