Fast multiplication and the PLWE–RLWE equivalence for an infinite family of maximal real subfields of cyclotomic fields

Thumbnail Image

Files

Fast_multiplication_and_the_PLWE_RLWE_equivalence_for_an_infinite_family_of_maximal_real_subfields_of_cyclotomic_fields.pdf (1.46 MB)

Access rights

openAccess
CC BY
publishedVersion

URL

Journal Title

Journal ISSN

Volume Title

A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2025-08

Department

Department of Mathematics and Systems Analysis

Major/Subject

Mcode

Degree programme

Language

en

Pages

23

Series

Designs, Codes and Cryptography, Volume 93, issue 8, pp. 2947-2969

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 n is the problem dimension. Finally, we provide a heuristic and theoretical comparison of the vulnerability to some attacks for the pth cyclotomic field versus the maximal totally real subextension of the 4pth cyclotomic field for a reasonable set of parameters of cryptographic size.

Description

Keywords

Ring Learning With Errors, Number-Theoretic Transform, Condition Number, Discrete Cosine Transform, Fast Multiplication, Polynomial Learning With Errors, Abelian Number Fields

Other note

DOI

10.1007/s10623-025-01601-3

Citation

Ahola, J, Blanco-Chacón, I, Bolaños, W, Haavikko, A, Hollanti, C & Sánchez-Ledesma, R M 2025, 'Fast multiplication and the PLWE–RLWE equivalence for an infinite family of maximal real subfields of cyclotomic fields', Designs, Codes and Cryptography, vol. 93, no. 8, pp. 2947-2969. https://doi.org/10.1007/s10623-025-01601-3

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202504163258

Collections

[article-cris] Perustieteiden korkeakoulu / SCI