Trace-based cryptanalysis of cyclotomic $R_{q,0}\times R_q$-PLWE for the non-split case

Abstract

We describe a decisional attack against a version of the PLWE problem in which the samples are taken from a certain proper subring of large dimension of the cyclotomic ring ${\mathbb{F}}_q[x]/({\Phi }_{p^k}(x))$ with $k>1$ in the case where $q\equiv 1(\mathrm{mod}p)$ but ${\Phi }_{p^k}(x)$ is not totally split over ${\mathbb{F}}_q$. Our attack uses the fact that the roots of ${\Phi }_{p^k}(x)$ over suitable extensions of ${\mathbb{F}}_q$ have zero-trace and has overwhelming success probability as a function of the number of input samples. An implementation in Maple and some examples of our attack are also provided.

20 pages; 1 figure; Minor updates as per referee's requests; formatted for publication

References in corpus (3)

• On the condition number of the Vandermonde matrix of the nth cyclotomic polynomial
• On the RLWE/PLWE equivalence for cyclotomic number fields
• RLWE/PLWE equivalence for the maximal totally real subextension of the $2^{r}pq$-th cyclotomic field