Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp:
E-Artikel
Titel:
RLWE and PLWE over cyclotomic fields are not equivalent
Beteiligte:
Di Scala, Antonio J.;
Sanna, Carlo;
Signorini, Edoardo
Erschienen:
Springer Science and Business Media LLC, 2024
Erschienen in:Applicable Algebra in Engineering, Communication and Computing
Sprache:
Englisch
DOI:
10.1007/s00200-022-00552-9
ISSN:
0938-1279;
1432-0622
Entstehung:
Anmerkungen:
Beschreibung:
<jats:title>Abstract</jats:title><jats:p>We prove that the Ring Learning With Errors (RLWE) and the Polynomial Learning With Errors (PLWE) problems over the cyclotomic field <jats:inline-formula><jats:alternatives><jats:tex-math>$${\mathbb {Q}}(\zeta _n)$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mrow>
<mml:mi>Q</mml:mi>
<mml:mo>(</mml:mo>
<mml:msub>
<mml:mi>ζ</mml:mi>
<mml:mi>n</mml:mi>
</mml:msub>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:math></jats:alternatives></jats:inline-formula> are not equivalent. Precisely, we show that reducing one problem to the other increases the noise by a factor that is more than polynomial in <jats:italic>n</jats:italic>. We do so by providing a lower bound, holding for infinitely many positive integers <jats:italic>n</jats:italic>, for the condition number of the Vandermonde matrix of the <jats:italic>n</jats:italic>th cyclotomic polynomial.</jats:p>