On the RLWE/PLWE equivalence for cyclotomic number fields

2020/01/29 by Iván Blanco Chacón, Chacón, Iván Blanco
Computer Science · #11T22 #11Z05 #68P25 #Coding theory and cryptography #Complexity and Algorithms in Graphs #Cryptography and Data Security #FOS: Mathematics #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.2001.10891

openalex publication_date 2020/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the equivalence between the Ring Learning With Errors and Polynomial Learning With Errors problems for cyclotomic number fields,namely: we prove that both problems are equivalent via a polynomial noise increase as long as the number of distinct primes dividing the conductor is kept constant. We refine our bound in the case where the conductor is divisible by at most three primes and we give an asymptotic subexponential formula for the condition number of the attached Vandermonde matrix valid for arbitrary degree.

Citations

• On lattices, learning with errors, random linear codes, and cryptography

Related

• RLWE and PLWE over cyclotomic fields are not equivalent
• Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Maximal Real Subfields of Cyclotomic Fields
• Provably weak instances of Ring-LWE
• On Ring Learning with Errors over the Tensor Product of Number Fields
• Ring-LWE Cryptography for the Number Theorist