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 29 Jun 2018

Contact author: damien stehle at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20180629:134419 (All versions of this report)

Short URL: ia.cr/2017/628