RLWE and PLWE over cyclotomic fields are not equivalent.

We prove that the Ring Learning With Errors (RLWE) and the Polynomial Learning With Errors (PLWE) problems over the cyclotomic field Q (ζ n) are not equivalent. Precisely, we show that reducing one problem to the other increases the noise by a factor that is more than polynomial in n. We do so by providing a lower bound, holding for infinitely many positive integers n, for the condition number of the Vandermonde matrix of the nth cyclotomic polynomial. [ABSTRACT FROM AUTHOR]