Paper 2017/628

Middle-Product Learning With Errors

Miruna Rosca, Amin Sakzad, Ron Steinfeld, and Damien Stehle

Abstract

We introduce a new variant $\text{MPLWE}$ of the Learning With Errors problem ($\text{LWE}$) making use of the Middle Product between polynomials modulo an integer~$q$. We exhibit a reduction from the Polynomial-$\text{LWE}$ problem ($\text{PLWE}$) parametrized by a polynomial~$f$, to $\text{MPLWE}$ which is defined independently of any such~$f$. The reduction only requires~$f$ to be monic with constant coefficient coprime with~$q$. It incurs a noise growth proportional to the so-called expansion factor of~$f$. We also describe a public-key encryption scheme with quasi-optimal asymptotic efficiency (the bit-sizes of the keys and the run-times of all involved algorithms are quasi-linear in the security parameter), which is secure against chosen plaintext attacks under the $$ hardness assumption. The scheme is hence secure under the assumption that $$ is hard for at least one polynomial~$$ of degree~$$ among a family of~$$'s which is exponential in~$$.