Middle-Product Learning With Errors (original) (raw)

Paper 2017/628

Middle-Product Learning With Errors

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

Abstract

We introduce a new variant MPLWE\MPLWEMPLWE 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\MPLWEMPLWE 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\MPLWEMPLWE hardness assumption. The scheme is hence secure under the assumption that PLWE\PLWEPLWE is hard for at least one polynomial~$f$ of degree~$n$ among a family of~$f$'s which is exponential in~$n$.

BibTeX

@misc{cryptoeprint:2017/628, author = {Miruna Rosca and Amin Sakzad and Ron Steinfeld and Damien Stehle}, title = {Middle-Product Learning With Errors}, howpublished = {Cryptology {ePrint} Archive, Paper 2017/628}, year = {2017}, url = {https://eprint.iacr.org/2017/628} }