On the Weakness of Ring-LWE mod Prime Ideal \(\mathfrak {q}\) by Trace Map

Lattice-based cryptography has attracted a great deal of attention due to the standardization of Post-Quantum Cryptography by the National Institute of Standards and Technology (NIST). The Ring-Learning with Error (Ring-LWE) problem is one of the mathematical problems that constitute such lattice cryptosystems, and it has many algebraic properties because it is considered in the ring of integers R of an algebraic number field K. This algebraic property makes it efficient, while it is also used for attacks. When the modulus q is unramified in K, it is known that the Ring-LWE problem, to determinate the secret information \(s\in R/qR\) , can be solved by determining \(s \,(\text {mod }\mathfrak {q})\) for all prime ideals \(\mathfrak {q}\) lying over q. The \(\chi ^2\) –attack determines \(s \,(\text {mod }\mathfrak {q})\) by using a statistical test over \(R/\mathfrak {q}\cong \mathbb F_{q^f}\) . The \(\chi ^2\) –attack is improved in the special case where the residue degree f is two, called the two–residue–degree \(\chi ^2\) –attack. In this paper, we extend the two-residue-degree \(\chi ^2\) –attack to the prime–residue–degree and composite–number–residue–degree \(\chi ^2\) –attack. Thus, the \(\chi ^2\) –attack in not only two but also any residue-degree case can efficiently work. As a result, the previous attacks on \((q,f) = (67,3)\) takes over 1.5 years but our attack takes only 129 s.