All-but-many lossy trapdoor functions and selective opening chosen-ciphertext security from LWE

Benoît Libert, Amin Sakzad, Damien Noel Stehle, Ron Steinfeld

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

    14 Citations (Scopus)

    Abstract

    Selective opening (SO) security refers to adversaries that receive a number of ciphertexts and, after having corrupted a subset of the senders (thus obtaining the plaintexts and the senders’ random coins), aim at breaking the security of remaining ciphertexts. So far, very few public-key encryption schemes are known to provide simulation-based selective opening (SIM-SO-CCA2) security under chosen-ciphertext attacks and most of them encrypt messages bit-wise. The only exceptions to date rely on all-but-many lossy trapdoor functions (as introduced by Hofheinz; Eurocrypt’12) and the Composite Residuosity assumption. In this paper, we describe the first all-but-many lossy trapdoor function with security relying on the presumed hardness of the Learning-With-Errors problem (LWE) with standard parameters. Our construction exploits homomorphic computations on lattice trapdoors for lossy LWE matrices. By carefully embedding a lattice trapdoor in lossy public keys, we are able to prove SIM-SO-CCA2 security under the LWE assumption. As a result of independent interest, we describe a variant of our scheme whose multi-challenge CCA2 security tightly relates to the hardness of LWE and the security of a pseudo-random function.

    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
    Pages332-364
    Number of pages33
    Volume10403 LNCS
    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
    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
    • Lossy trapdoor functions
    • Chosen-ciphertext security
    • Selective-opening security
    • Tight security reductions

    Cite this

    Libert, B., Sakzad, A., Stehle, D. N., & Steinfeld, R. (2017). All-but-many lossy trapdoor functions and selective opening chosen-ciphertext security from LWE. In J. Katz, & H. Shacham (Eds.), Advances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings (Vol. 10403 LNCS, pp. 332-364). (Lecture Notes in Computer Science; Vol. 10403). Springer. https://doi.org/10.1007/978-3-319-63697-9_12