**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.

**Category / Keywords: **lattice-based cryptography, LWE, PLWE

**Original Publication**** (with major differences): **SECITC 2018

**Date: **received 25 Oct 2018, last revised 15 Nov 2018

**Contact author: **madalinabolboceanu at gmail com

**Available format(s): **PDF | BibTeX Citation

**Note: **fixed typos

**Version: **20181115:160148 (All versions of this report)

**Short URL: **ia.cr/2018/1035

[ Cryptology ePrint archive ]