Paper 2017/628

Middle-Product Learning With Errors

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


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

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2017
Contact author(s)
damien stehle @ gmail com
2018-12-11: last of 4 revisions
2017-06-27: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.