Attacks on search RLWE

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.