A Fast Multiplication Algorithm and RLWE–PLWE Equivalence for the Maximal Real Subfield of the 2 r p s 2^{r}p^{s} -th Cyclotomic Field
Wilmar Bolaños, Antti Haavikko, Rodrigo M. Sánchez-Ledesma · 2025
Read A Fast Multiplication Algorithm and RLWE–PLWE Equivalence for the Maximal Real Subfield of the 2 r p s 2^{r}p^{s} -th Cyclotomic Field by Wilmar Bolaños, Antti Haavikko, Rodrigo M. Sánchez-Ledesma (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-05159.txt.
Introduction
Wilmar Bolanos, Antti Haavikko, and Rodrigo Sanchez-Ledesma prove results that matter for lattice-based codes, in a 2025 paper. Their setting is a family of number fields built from roots of unity. Two forms of a hard problem, one on rings and one on polynomials, are shown to match in this setting. That match rests on a bound for a key transform.
The authors also give a fast way to multiply in these rings. The method uses a cosine transform and runs in near-linear time. Both results extend earlier work that covered only a single prime case. Fast, safe math of this kind underpins proposed codes that aim to resist future quantum attacks.
Catalog record
| CREATOR | Wilmar Bolaños, Antti Haavikko, Rodrigo M. Sánchez-Ledesma |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-05159
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Fast Multiplication Algorithm and RLWE–PLWE Equivalence for the Maximal Real Subfield of the 2 r p s 2^{r}p^{s} -th Cyclotomic Field Wilmar Bolaños, Antti Haavikko, Rodrigo M. Sánchez-Ledesma Abstract This paper proves the RLWE–PLWE equivalence for the maximal real subfields of the cyclotomic fields with conductor n = 2 r p s n=2^{r}p^{s} , where p p is an odd prime, and r ≥ 0 r\geq 0 and s ≥ 1 s\geq 1 are integers. In particular, we show that the canonical embedding as a linear transform has a condition number bounded above by a polynomial in n n . In addition, we describe a fast multiplication algorithm in the ring of integers of these real subfields. The multiplication algorithm uses the fast Discrete Cosine Transform (DCT) and has computational complexity 𝒪 ( n log n ) \mathcal{O}(n\log n) . Both the proof of the RLWE–PLWE equivalence and the fast multiplication algorithm are generalizations of the results in [ 3 ] , where the same claims are proved for a single prime p = 3 p=3 . Keywords: ring learning with errors, polynomial learning with errors, fast multiplication, discrete cosine transform 1 Introduction Lattice-based cryptography has emerged as a promising candidate for post-quantum cryptography, offering potential resilience against attacks by quantum computers. The Learning with Errors (LWE) problem and its variants, Ring-LWE (RLWE) and Polynomial-LWE (PLWE), are fundamental hardness assumptions in the field of post-quantum cryptography (PQC). These problems involve finding approximate solutions to noisy linear systems, and RLWE and PLWE have a performance advantage over the unstructured LWE due to their inherent algebraic structure. The origins of RLWE and PLWE can be traced back to the seminal works of Stehlé et al. [ 31 ] and Lyubashevsky et al. [ 22 ] . Since their discoveries, the relationship between the RLWE and PLWE problems has been an active area of research. RLWE is generally considered to be more secure because of its connection to well-established lattice problems. Also, the abstract setting of the RLWE problem is fitting for theoretical proofs. On the other hand, PLWE offers practical advantages regarding implementation and performance, particularly for multiplication operations. When it comes to other areas of modern cryptography, fast multiplication algorithms play a substantial role also in Homomorphic Encryption (HE), especially in schemes that derive from the structured LWE variants. In general, HE schemes use larger parameters than PQC schemes and hence benefit more from improvements in the asymptotic complexity of multiplication. Prior research has established the equivalence between RLWE and PLWE for specific families of number fields and polynomials. For non-cyclotomic number fields, the work of Ahola et al. [ 3 ] demonstrated this equivalence for the maximal totally real subfield of the 2^{r}3^{s} -th cyclotomic field, along with a fast multiplication algorithm based on the Discrete Cosine Transform (DCT). Also, the work in [ 30 , Section 4] focused on two large non-cyclotomic families of polynomials and proved that the related Vandermonde matrices have polynomially bounded condition numbers. In the cyclotomic case, notable contributions include the work of Ducas and Durmus [ 15 ] , who proved the equivalence for cyclotomic number fields of degree 2^{k}p or 2^{k}pq , where p and q are primes and q\neq p . Furthermore, Di Scala et al. [ 14 ] showed that RLWE and PLWE are not equivalent in general if no restrictions are imposed on the conductor of the cyclotomic field. However, Blanco-Chacón [ 7 ] proved that the RLWE–PLWE equivalence holds if the conductor of the cyclotomic field is divisible by a bounded number of primes. Later, Araujo [ 12 ] showed the equivalence for any cyclic number field of odd prime degree, which by the Kronecker–Weber theorem is a subfield of some cyclotomic field. Regarding the hardness of the structured lattices, [ 11 ] uses Stickelberger ideals from class field theory to prove the existence of a quantum polynomial-time attack against ideal lattices of cyclotomic number fields. Their results assume the Generalized Riemann Hypothesis and impose some class-field theoretical restrictions on the cyclotomic fields. The exact claim is the following: Theorem . There exists a quantum polynomial-time algorithm, that for a cyclotomic number field K of prime power conductor and any ideal \mathfrak{a} of \mathfrak{O}_{K} , returns an element v\in\mathfrak{a} with Euclidean norm \displaystyle||v||\leq\operatorname{N}(\mathfrak{a})^{1/n}\operatorname{exp}(\tilde{\mathcal{O}}(\sqrt{n})). Note that the ideals in the ring of integers of the maximal real subfields of cyclotomic fields are not ideals in the ring of integers of the cyclotomic field containing the subfield. Therefore, the quantum attack of [ 11 ] does not apply to the maximal real subfields. This paper extends the results of [ 3 ] by generalizing the fast multiplication algorithm and the equivalence between RLWE and PLWE to the maximal real subfield of the 2^{r}p^{s} -th cyclotomic field, where p is an arbitrary odd prime. This generalization comes with many technical lemmas and verifications guaranteeing that the security and speed of the RLWE or PLWE schemes are not compromised. The main contributions of this paper are: 1. A proof of the equivalence between RLWE and PLWE for maximal real subfields of cyclotomic fields with conductor n=2^{r}p^{s} . 2. A fast multiplication algorithm with quasilinear complexity for elements in the ring of integers of these subfields, utilizing the Discrete Cosine Transform. 3. Explicit algorithms for the change of basis between the power basis and the modified Chebyshev basis, enabling efficient computations regardless of the basis. While the use of maximal real cyclotomic polynomials in PLWE is new, they are not merely an artifact of [ 3 ] and this work. The study of the relevant security properties of PLWE schemes under these polynomials, along with the development of fast multiplication techniques, is a result of a growing interest in finding applicable non-cyclotomic PLWE instances. Regarding applications, the support for the maximal real polynomials has already been incorporated into new cryptographic libraries (see LATTIGO [ 18 ] ). The structure of the paper is as follows. In Section 2 , we introduce the necessary background on maximal real cyclotomic polynomials, matrix norms, and properties of certain cosine matrices related to the canonical embedding of the number fields at play. We give bounds on the Frobenius norms of these cosine matrices and use the result in the proofs of the two main theorems. Section 2 also provides the full definitions of the RLWE and PLWE distributions. Section 3 covers the \mathbb{Q} -linear dependencies between elements of the form 2\cos(2\pi j/n) for two cases of conductor, namely n=p^{s} and n=2^{r}p^{s} . Throughout the paper, we study these two cases for n separately. We derive explicit formulas for the minimal polynomials \Psi_{n}(x) of the primitive elements \psi_{n}=2\cos(2\pi/n) given in the basis of modified Chebyshev polynomials V_{j}(x) that are introduced in Section 2 . We describe in detail the reduction of polynomials to small degree representatives in the polynomial quotient ring \mathbb{Z}[x]/(\Psi_{n}(x)) , again using the Chebyshev basis. These formulas will play an integral part in the proof of all four main theorems of the paper. Section 4 tackles the PLWE–RLWE equivalence of the maximal real subfields of cyclotomic fields with conductor n as above. The two main theorems of Section 4 combine