Trace-based cryptoanalysis of cyclotomic PLWE for the non-split case. (arXiv:2209.11962v1 [cs.CR])

We provide an attack against the decision version of PLWE over the cyclotomic
ring $\mathbb{F}_q[x]/(\Phi_{p^k}(x))$ with $k>1$ in the case where $q\equiv
1\pmod{p}$ but $\Phi_{p^k}(x)$ is not totally split over $\mathbb{F}_q$. Our
attack uses that the roots of $\Phi_{p^k}(x)$ over suitable extensions of
$\mathbb{F}_q$ have zero-trace and has overwhelming success probability in
function of the number of samples taken as input. An implementation in Maple
and some examples of our attack are also provided.

case non trace