Welcome to the resource topic for 2017/628
Title:
Middle-Product Learning With Errors
Authors: Miruna Rosca, Amin Sakzad, Ron Steinfeld, 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.
ePrint: https://eprint.iacr.org/2017/628
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .