Paper 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.
Metadata
- Available format(s)
- Publication info
- A minor revision of an IACR publication in CRYPTO 2017
- Contact author(s)
- damien stehle @ gmail com
- History
- 2018-12-11: last of 4 revisions
- 2017-06-27: received
- See all versions
- Short URL
- https://ia.cr/2017/628
- License
-
CC BY