Relating Different Polynomial-LWE Problems

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 than \(\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.