Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Maximal Real Subfields of Cyclotomic Fields

Joonas Ahola; Iván Blanco-Chacón; Wilmar Bolaños; Antti Haavikko; Camilla Hollanti; Rodrigo M. Sánchez-Ledesma

Paper 2024/1899

Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Maximal Real Subfields of Cyclotomic Fields

Joonas Ahola, Aalto University

Iván Blanco-Chacón

, Universidad de Alcalá

Wilmar Bolaños

, Aalto University

Antti Haavikko, Universidad de Alcalá

Camilla Hollanti

, Aalto University

Rodrigo M. Sánchez-Ledesma

, Complutense University of Madrid

Abstract

We prove the equivalence between the Ring Learning With Errors (RLWE) and the Polynomial Learning With Errors (PLWE) problems for the maximal totally real subfield of the -th cyclotomic field for and . Moreover, we describe a fast algorithm for computing the product of two elements in the ring of integers of these subfields. This multiplication algorithm has quasilinear complexity in the dimension of the field, as it makes use of the fast Discrete Cosine Transform (DCT). Our approach assumes that the two input polynomials are given in a basis of Chebyshev-like polynomials, in contrast to the customary power basis. To validate this assumption, we prove that the change of basis from the power basis to the Chebyshev-like basis can be computed with arithmetic operations, where is the problem dimension. Finally, we provide a heuristic and theoretical comparison of the vulnerability to some attacks for the -th cyclotomic field versus the maximal totally real subextension of the -th cyclotomic field for a reasonable set of parameters of cryptographic size.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Minor revision. arXiv
DOI: 10.48550/arXiv.2410.00792
Keywords: Number Theoretic Transform Discrete Cosine Transform Ring Learning with Errors Polynomial Learning with Errors
Contact author(s): joonas ahola @ aalto fi
ivan blancoc @ uah es
wilmar bolanos @ aalto fi
anttijhaavikko @ gmail com
camilla hollanti @ aalto fi
rodrma01 @ ucm es
History: 2025-02-18: revised; 2024-11-22: received; See all versions
Short URL: https://ia.cr/2024/1899
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1899,
      author = {Joonas Ahola and Iván Blanco-Chacón and Wilmar Bolaños and Antti Haavikko and Camilla Hollanti and Rodrigo M. Sánchez-Ledesma},
      title = {Fast Multiplication and the {PLWE}-{RLWE} Equivalence for an Infinite Family of Maximal Real Subfields of Cyclotomic Fields},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1899},
      year = {2024},
      doi = {10.48550/arXiv.2410.00792},
      url = {https://eprint.iacr.org/2024/1899}
}