Cryptology ePrint Archive: Report 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$.

Category / Keywords:

Original Publication (with minor differences): IACR-CRYPTO-2017

Date: received 26 Jun 2017, last revised 11 Dec 2018

Contact author: damien stehle at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20181211:151127 (All versions of this report)

Short URL: ia.cr/2017/628