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
[ Cryptology ePrint archive ]