A fast multiplication algorithm and RLWE–PLWE equivalence for the maximal real subfield of the $ 2^r p^s $-th cyclotomic field

Wilmar Bolaños; Antti Haavikko; Rodrigo M. Sánchez-Ledesma

doi:10.3934/amc.2025051

Article Contents

2026, Volume 21: 212-238. Doi: 10.3934/amc.2025051

This volume Previous Article Hulls of $\mathbb Z_p\mathbb Z_p[v] $-cyclic codes and construction of EAQECCs Next Article Construction and enumeration of self-orthogonal, self-dual and complementary-dual Eisenstein additive cyclic codes over finite commutative chain rings

A fast multiplication algorithm and RLWE–PLWE equivalence for the maximal real subfield of the $ 2^r p^s $-th cyclotomic field

1.
Fundación Universitaria Konrad Lorenz, Colombia
2.
Universidad de Alcalá, Spain
3.
Universidad Complutense de Madrid / Indra Sistemas de Comunicaciones Seguras, Spain

^*Corresponding author: Antti Haavikko
^*Corresponding author: Antti Haavikko

Received: May 2025

Revised: October 2025

Early access: October 23, 2025

Published online: October 23, 2025

Abstract / Introduction Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by

Abstract

This paper proves the RLWE–PLWE equivalence for the maximal real subfields of the cyclotomic fields with conductor $ n = 2^r p^s $, where $ p $ is an odd prime, and $ r \geq 0 $ and $ s \geq 1 $ are integers. In particular, we show that the canonical embedding as a linear transformation has a condition number bounded above by a polynomial in $ 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 $ \mathcal{O}(n \log n) $. This work extends the results of Ahola et al., where the same claims are proved for a single prime $ p = 3 $.

Keywords:

Mathematics Subject Classification: Primary: 94A60; Secondary: 11R80, 11T06.

Citation:

Full Text(HTML)

Table 1. Vulnerability ratio of root-based attacks for $ \Psi_{2^r p^s}(x) $ for $ (p, s, r) \in S $, $ q \in [2048, 4096] $ and $ \sigma \in [2, 7] $, based on roots and $ k $-ideal factors of $ \Psi_{2^r p^s}(x) $

	$ \sigma = 2 $	$ \sigma = 3 $	$ \sigma = 4 $	$ \sigma = 5 $	$ \sigma = 6 $	$ \sigma = 7 $
Small set (roots)	0	0	0	0	0	0
Small error (roots)	0.0003	0.0003	0.0003	0.0003	0.0003	0.0003
Small set ($ k $-ideal)	0	0	0	0	0	0
Small error ($ k $-ideal)	0.0008	0.0008	0.0008	0.0008	0.0008	0.0008

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	R. C. Agarwal and C. S. Burrus, Number theoretic transforms to implement fast digital convolution, Proceedings of the IEEE, 63 (1975), 550-560. doi: 10.1109/PROC.1975.9791.
[2]	N. Ahmed, T. Natarajan and K. R. Rao, Discrete cosine transform, IEEE Transactions on Computers, C-23 (1974), 90-93. doi: 10.1109/T-C.1974.223784.
[3]	J. Ahola, I. Blanco-Chacón, W. Bolaños, A. Haavikko, C. Hollanti and R. M. Sánchez-Ledesma, Fast multiplication and the PLWE-RLWE equivalence for an infinite family of maximal real subfields of cyclotomic fields, Designs, Codes and Cryptography, 93 (2025), 2947-2969.
[4]	B. Barbero-Lucas, I. Blanco-Chacón, R. Durán-Díaz and R. Y. Njah Nchiwo, Cryptanalysis of PLWE based on zero-trace quadratic roots, preprint, (2023), arXiv: 2312.11533.
[5]	G. Bi, Fast algorithms for type-Ⅲ DCT of composite sequence lengths, IEEE Transactions on Signal Processing, 47 (1999), 2053-2059. doi: 10.1109/78.771055.
[6]	G. Bi and L.W. Yu, DCT algorithms for composite sequence lengths, IEEE Transactions on Signal Processing, 46 (1998), 554-562. doi: 10.1109/78.661324.
[7]	I. Blanco-Chacón, On the RLWE/PLWE equivalence for cyclotomic number fields, Appl. Algebra Eng., Commun. Comput., 33 (2022), 53-71. doi: 10.1007/s00200-020-00433-z.
[8]	I. Blanco-Chacón, RLWE/PLWE equivalence for totally real cyclotomic subextensions via quasi-Vandermonde matrices, Journal of Algebra and Its Applications, 22 (2022), 2250218, 18 pp. doi: 10.1142/S0219498822502188.
[9]	I. Blanco-Chacón, R. Durán-Díaz and R. M. Sanchéz-Ledesma, A generalized approach to root-based attacks towards PLWE, preprint, (2024), arXiv: 2410.01017.
[10]	I. Blanco-Chacón and L. López-Hernanz, RLWE/PLWE equivalence for the maximal totally real subextension of the $2^rpq$-th cyclotomic field, Advances in Mathematics of Communications, 18 (2024), 1343-1363. doi: 10.3934/amc.2022093.
[11]	R. Cramer, L. Ducas and B. Wesolowski, Short Stickelberger class relations and application to Ideal-SVP, Advances in cryptology-EUROCRYPT, Lecture Notes in Comput. Sci., 10210 (2017), 324-348. doi: 10.1007/978-3-319-56620-7_12.
[12]	R. R. de Araujo, The condition number associated with ideal lattices from odd prime degree cyclic number fields, Journal of Mathematical Cryptology, 19 (2025), 20240022, 6 pp. doi: 10.1515/jmc-2024-0022.
[13]	M. M. C. de Souza, H. M. de Oliveira, R. M. C. de Souza and M. M. Vasconcelos, The discrete cosine transform over prime finite fields, Proceedings of the Telecommunications and Networking-ICT 2004: 11th International Conference on Telecommunications, (2004), 482-487. doi: 10.1007/978-3-540-27824-5_65.
[14]	A. J. Di Scala, C. Sanna and E. Signorini, RLWE and PLWE over cyclotomic fields are not equivalent, Appl. Algebra Eng., Commun. Comput., 35 (2024), 351-358. doi: 10.1007/s00200-022-00552-9.
[15]	L. Ducas and A. Durmus, Ring-LWE in polynomial rings, Proceedings of the PKC 2012: International Workshop on Public Key Cryptography, Lecture Notes in Comput. Sci., 7293 (2012), 34-51. doi: 10.1007/978-3-642-30057-8_3.
[16]	Y. Elias, K. E. Lauter, E. Ozman and K. E. Stange, Ring-LWE Cryptography for the number theorist, Proceedings of the 2014 WIN3 Workshop, 3 (2014), 271-290.
[17]	Y. Elias, K. E. Lauter, E. Ozman and K. E. Stange, Provably weak instances of ring-LWE, Proceedings of Annual Cryptology Conference: CRYPTO 2015, 9215 (2015), 63-92.
[18]	Tune Insight SA EPFL-LDS, Lattigo v6, (2024), available from: https://github.com/tuneinsight/lattigo.
[19]	H. Hou, A fast recursive algorithm for computing the discrete cosine transform, IEEE Transactions on Acoustics, Speech, and Signal Processing, 35 (1987), 1455-1461. doi: 10.1109/TASSP.1987.1165060.
[20]	C. W. Kok, Fast algorithm for computing discrete cosine transform, IEEE Transactions on Signal Processing, 45 (1997), 757-760. doi: 10.1109/78.558495.
[21]	K. A. Loper and N. J. Werner, Resultants of minimal polynomials of maximal real cyclotomic extensions, Journal of Number Theory, 158 (2016), 298-315. doi: 10.1016/j.jnt.2015.06.002.
[22]	V. Lyubashevsky, C. Peikert and O. Regev, On ideal lattices and learning with errors over rings, Proceedings of EUROCRYPT 2010: Annual International Conference on the Theory and Applications of Cryptographic Techniques, 6110 (2010), 1-23. doi: 10.1007/978-3-642-13190-5_1.
[23]	V. Lyubashevsky and G. Seiler, NTTRU: Truly fast NTRU using NTT, IACR Transactions on Cryptographic Hardware and Embedded Systems, (2019), 180-201. doi: 10.46586/tches.v2019.i3.180-201.
[24]	National Institute of Standards and Technology (NIST), Computer Security Resource Center, Technical Report: Module-Lattice-Based Digital Signature Standard, 2024, available from: https://csrc.nist.gov/pubs/fips/204/final.
[25]	National Institute of Standards and Technology (NIST), Computer Security Resource Center, Technical Report: Module-Lattice-Based Key-Encapsulation Mechanism Standard, 2024, available from: https://csrc.nist.gov/pubs/fips/203/final.
[26]	National Institute of Standards and Technology (NIST), Computer Security Resource Center, Technical Report: Stateless Hash- Based Digital Signature Standard, 2024, Available from: https://csrc.nist.gov/pubs/fips/205/final.
[27]	V. Y. Pan, New fast algorithms for polynomial interpolation and evaluation on the Chebyshev node set, Computers & Mathematics with Applications, 35 (1998), 125-129.
[28]	J. M. Pollard, The fast Fourier transform in a finite field, Mathematics of Computation, 25 (1971), 365-374. doi: 10.1090/S0025-5718-1971-0301966-0.
[29]	T. Prest, P. A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Ricosset, G. Seiler, W. Whyte and Z. Zhang., National Institute of Standards and Technology (NIST), Computer Security Resource Center, Technical Report: Post-Quantum Cryptography Standardization - Round 3 Submissions, 2024, available from: https://csrc.nist.gov/Projects/post-quantum-cryptography/round-4-submissions.
[30]	M. Rosca, D. Stehlé and A. Wallet, On the ring-LWE and polynomial-LWE problems, Proceedings of EUROCRYPT 2018: Annual International Conference on The Theory and Applications of Cryptographic Techniques, 10820 (2018), 146-173. doi: 10.1007/978-3-319-78381-9_6.
[31]	D. Stehlé, R. Steinfeld, K. Tanaka and K. Xagawa, Efficient public key encryption based on ideal lattices, Proceedings of ASIACRYPT 2009: Annual International Conference on the Theory and Applications of Cryptographic Techniques, 5912 (2009), 617-635. doi: 10.1007/978-3-642-10366-7_36.
[32]	L. C. Washington, Introduction to Cyclotomic Fields, 1$^{st}$ edition, Springer Science & Business Media, Berlin, 2012.