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

    Abstract

    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
    PublisherSpringer
    Pages283-297
    Number of pages15
    Volume10403
    ISBN (Electronic)9783319636979
    ISBN (Print)9783319636962
    DOIs
    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)
    Volume10403
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    ConferenceAdvances in Cryptology 2017
    Abbreviated titleCRYPTO 2017
    CountryUnited States of America
    CitySanta Barbara
    Period20/08/1724/08/17

    Keywords

    • 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 ). Cham Switzerland: Springer. https://doi.org/10.1007/978-3-319-63697-9_10
    Roşca, Miruna ; Sakzad, Amin ; Stehle, Damien Noel ; Steinfeld, Ron. / Middle-product learning with errors. Advances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings. editor / Jonathan Katz ; Hovav Shacham. Vol. 10403 Cham Switzerland : Springer, 2017. pp. 283-297 (Lecture Notes in Computer Science ).
    @inproceedings{437f94a167e74ae09bb4fcaafaa6b951,
    title = "Middle-product learning with errors",
    abstract = "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.",
    keywords = "LWE, PLWE, Public-key encryption",
    author = "Miruna Roşca and Amin Sakzad and Stehle, {Damien Noel} and Ron Steinfeld",
    year = "2017",
    doi = "10.1007/978-3-319-63697-9_10",
    language = "English",
    isbn = "9783319636962",
    volume = "10403",
    series = "Lecture Notes in Computer Science",
    publisher = "Springer",
    pages = "283--297",
    editor = "Katz, {Jonathan } and Shacham, {Hovav }",
    booktitle = "Advances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings",

    }

    Roşca, M, Sakzad, A, Stehle, DN & 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, Lecture Notes in Computer Science , vol. 10403 , Springer, Cham Switzerland, pp. 283-297, Advances in Cryptology 2017, Santa Barbara, United States of America, 20/08/17. https://doi.org/10.1007/978-3-319-63697-9_10

    Middle-product learning with errors. / Roşca, Miruna; Sakzad, Amin; Stehle, Damien Noel; Steinfeld, Ron.

    Advances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings. ed. / Jonathan Katz; Hovav Shacham. Vol. 10403 Cham Switzerland : Springer, 2017. p. 283-297 (Lecture Notes in Computer Science ; Vol. 10403 ).

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

    TY - GEN

    T1 - Middle-product learning with errors

    AU - Roşca, Miruna

    AU - Sakzad, Amin

    AU - Stehle, Damien Noel

    AU - Steinfeld, Ron

    PY - 2017

    Y1 - 2017

    N2 - 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.

    AB - 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.

    KW - LWE

    KW - PLWE

    KW - Public-key encryption

    UR - http://www.scopus.com/inward/record.url?scp=85028458328&partnerID=8YFLogxK

    U2 - 10.1007/978-3-319-63697-9_10

    DO - 10.1007/978-3-319-63697-9_10

    M3 - Conference Paper

    SN - 9783319636962

    VL - 10403

    T3 - Lecture Notes in Computer Science

    SP - 283

    EP - 297

    BT - Advances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings

    A2 - Katz, Jonathan

    A2 - Shacham, Hovav

    PB - Springer

    CY - Cham Switzerland

    ER -

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