Paper 2018/1035

Relating different Polynomial-LWE problems

Madalina Bolboceanu

Abstract

In this paper we focus on Polynomial Learning with Errors (PLWE). This problem is parametrized by a polynomial and we are interested in relating the hardness of the $\text{PLWE}^f$ and $\text{PLWE}^h$ problems for different polynomials $f$ and $h$. More precisely, our main result shows that for a fixed monic polynomial $f$, $\text{PLWE}^{f\circ g}$ is at least as hard as $\text{PLWE}^f$, in both search and decision variants, for any monic polynomial $g$. As a consequence, $\text{PLWE}^{\phi_n}$ is harder than $\text{PLWE}^{f},$ for a minimal polynomial $f$ of an algebraic integer from the cyclotomic field $\mathbb{Q}(\zeta_n)$ with specific properties. Moreover, we prove in decision variant that in the case of power-of-2 polynomials, $\text{PLWE}^{\phi_n}$ is at least as hard as $\text{PLWE}^f,$ for a minimal polynomial $f$ of algebraic integers from the $n$th cyclotomic field with weaker specifications than those from the previous result.

Note: fixed typos

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. MAJOR revision.SECITC 2018
Keywords
lattice-based cryptographyLWEPLWE
Contact author(s)
madalinabolboceanu @ gmail com
History
2018-11-15: revised
2018-10-30: received
See all versions
Short URL
https://ia.cr/2018/1035
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1035,
      author = {Madalina Bolboceanu},
      title = {Relating different Polynomial-LWE problems},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1035},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1035}},
      url = {https://eprint.iacr.org/2018/1035}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.