|
|||||
 |
|
|
|
|
|
|
|
Spectral
distortion and the ring learning with errors problem
Liljana Babinkostova, Ariana G. Chin, Aaron Kirtland, Vladyslav Nazarchuk and Esther Plotnick |
|
Vol. 18 (2025), No. 2, 181–198
|
Abstract |
|
Certain attacks on the ring learning with errors (RLWE) problem rely on reduction to the polynomial variant (PLWE) of the problem. The spectral distortion is used to measure the RLWE-to-PLWE reduction. We investigate the spectral distortion and answer questions posed by Y. Elias et al. (2016) regarding spectral distortion used as a condition for a successful attack. We provide a closed form for the spectral distortion of certain classes of cyclotomic polynomials. Moreover, we present a bound on the spectral distortion of cyclotomic polynomials. |
Keywords
learning with errors, spectral distortion, cyclotomic
polynomials
|
Mathematical Subject Classification
Primary: 11T71, 94A60
Secondary: 11C20, 15B05
|
Milestones
Received: 4 February 2022
Revised: 21 September 2022
Accepted: 10 September 2023
Published: 26 February 2025
Communicated by Kenneth S. Berenhaut
|
Authors |
| Liljana Babinkostova | |
| Department of Mathematics Boise State University Boise, ID United States |
|
| Ariana G. Chin | |
| Department of Mathematics University of California Los Angeles, CA United States |
|
| Aaron Kirtland | |
| Washington University in St.
Louis St. Louis, MO United States |
|
| Vladyslav Nazarchuk | |
| Yale University New Haven, CT United States |
|
| Esther Plotnick | |
| Harvard University Cambridge, MA United States |
|
| © 2025 MSP (Mathematical Sciences Publishers). |
