Trace-based cryptanalysis of cyclotomic R_{q,0}xR_q-PLWE for the non-split case

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 Fq[x]/(Φp k (x)) with k > 1 in the case where q ≡ 1 (mod p) but Φp k (x) is not totally split over Fq. Our attack uses the fact that the roots of Φp k (x) over suitable extensions of Fq 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.Agencia Estatal de InvestigaciónUniversidad de Alcal