2022/01/12 by Antonio J. Di Scala, Carlo Sanna, Di Scala, Antonio J. +3
Computer Science · #Coding theory and cryptography #Quantum Computing Algorithms and Architecture #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2201.04365
We prove that the Ring Learning With Errors (RLWE) and the Polynomial Learning With Errors (PLWE) problems over the cyclotomic field ℚ(ζ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.