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

    26 Citations (Scopus)


    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
    Number of pages33
    Volume10403 LNCS
    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: 37th (Proceedings)

    Publication series

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


    ConferenceAdvances in Cryptology 2017
    Abbreviated titleCRYPTO 2017
    Country/TerritoryUnited States of America
    CitySanta Barbara
    Internet address


    • LWE
    • Lossy trapdoor functions
    • Chosen-ciphertext security
    • Selective-opening security
    • Tight security reductions

    Cite this