Welcome to the resource topic for 2018/1035
Title:
Relating different Polynomial-LWE problems
Authors: 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.
ePrint: https://eprint.iacr.org/2018/1035
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .