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}}^{{\varphi }_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}}^{{\varphi }_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