Paper 2017/628

Middle-Product Learning With Errors

Miruna Rosca and Amin Sakzad and Ron Steinfeld and Damien Stehle

Abstract

We introduce a new variant $\MPLWE$ of the Learning With Errors problem ($\LWE$) making use of the Middle Product between polynomials modulo an integer~$q$. We exhibit a reduction from the Polynomial-$\LWE$ problem ($\PLWE$) parametrized by a polynomial~$f$, to $\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 $\MPLWE$ hardness assumption. The scheme is hence secure under the assumption that $\PLWE$ is hard for at least one polynomial~$f$ of degree~$n$ among a family of~$f$'s which is exponential in~$n$.