Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Maximal Real Subfields of Cyclotomic Fields
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909498729299968 |
|---|---|
| author | Ahola, Joonas Blanco-Chacón, Iván Bolaños, Wilmar Haavikko, Antti Hollanti, Camilla Sánchez-Ledesma, Rodrigo Martín |
| author_facet | Ahola, Joonas Blanco-Chacón, Iván Bolaños, Wilmar Haavikko, Antti Hollanti, Camilla Sánchez-Ledesma, Rodrigo Martín |
| contents | 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 $2^r 3^s$-th cyclotomic field for $r \geq 3$ and $s \geq 1$. 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 $\mathcal{O}(n \log n)$ arithmetic operations, where $n$ is the problem dimension. Finally, we provide a heuristic and theoretical comparison of the vulnerability to some attacks for the $p$-th cyclotomic field versus the maximal totally real subextension of the $4p$-th cyclotomic field for a reasonable set of parameters of cryptographic size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_00792 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Maximal Real Subfields of Cyclotomic Fields Ahola, Joonas Blanco-Chacón, Iván Bolaños, Wilmar Haavikko, Antti Hollanti, Camilla Sánchez-Ledesma, Rodrigo Martín Cryptography and Security Number Theory 11T71 (Primary), 94A60 (Secondary) 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 $2^r 3^s$-th cyclotomic field for $r \geq 3$ and $s \geq 1$. 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 $\mathcal{O}(n \log n)$ arithmetic operations, where $n$ is the problem dimension. Finally, we provide a heuristic and theoretical comparison of the vulnerability to some attacks for the $p$-th cyclotomic field versus the maximal totally real subextension of the $4p$-th cyclotomic field for a reasonable set of parameters of cryptographic size. |
| title | Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Maximal Real Subfields of Cyclotomic Fields |
| topic | Cryptography and Security Number Theory 11T71 (Primary), 94A60 (Secondary) |
| url | https://arxiv.org/abs/2410.00792 |