# [Resource Topic] 2018/1035: Relating different Polynomial-LWE problems

Welcome to the resource topic for 2018/1035

Title:
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 \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.