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

We describe a decisional attack against a version of the PLWE problem inwhich the samples are taken from a certain proper subring of large dimension ofthe cyclotomic ring $\mathbb{F}_q[x]/(\Phi_{p^k}(x))$ with $k>1$ in the casewhere $q\equiv 1\pmod{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)$ oversuitable extensions of $\mathbb{F}_q$ have zero-trace and has overwhelmingsuccess probability as a function of the number of input samples. Animplementation in Maple and some examples of our attack are also provided.Comment: 20 pages; 1 figure; Minor updates as per referee's requests; formatted for publicatio