Middle-product learning with errors

Miruna Roşca, Amin Sakzad, Damien Noel Stehle, Ron Steinfeld

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    9 Citations (Scopus)


    We introduce a new variant MP LWE 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 MP-LWE 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 MP-LWE 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.

    Original languageEnglish
    Title of host publicationAdvances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings
    EditorsJonathan Katz, Hovav Shacham
    Place of PublicationCham Switzerland
    Number of pages15
    ISBN (Electronic)9783319636979
    ISBN (Print)9783319636962
    Publication statusPublished - 2017
    EventAdvances in Cryptology 2017 - Santa Barbara, United States of America
    Duration: 20 Aug 201724 Aug 2017
    Conference number: 37

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer International (AG)
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    ConferenceAdvances in Cryptology 2017
    Abbreviated titleCRYPTO 2017
    CountryUnited States of America
    CitySanta Barbara


    • LWE
    • PLWE
    • Public-key encryption

    Cite this

    Roşca, M., Sakzad, A., Stehle, D. N., & Steinfeld, R. (2017). Middle-product learning with errors. In J. Katz, & H. Shacham (Eds.), Advances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings (Vol. 10403, pp. 283-297). (Lecture Notes in Computer Science ; Vol. 10403 ). Springer. https://doi.org/10.1007/978-3-319-63697-9_10