Paper 2022/1229

Cumulatively All-Lossy-But-One Trapdoor Functions from Standard Assumptions

Benoît Libert, ENS de Lyon, Laboratoire LIP (U. Lyon, CNRS, ENSL, Inria, UCBL), France, CNRS, Laboratoire LIP, France
Ky Nguyen, DI ENS, École normale supérieure, Université PSL, CNRS, INRIA, 75005 Paris, France
Alain Passelègue, ENS de Lyon, Laboratoire LIP (U.\ Lyon, CNRS, ENSL, Inria, UCBL), France, Inria, France

Chakraborty, Prabhakaran, and Wichs (PKC'20) recently introduced a new tag-based variant of lossy trapdoor functions, termed cumulatively all-lossy-but-one trapdoor functions (CALBO-TDFs). Informally, CALBO-TDFs allow defining a public tag-based function with a (computationally hidden) special tag, such that the function is lossy for all tags except when the special secret tag is used. In the latter case, the function becomes injective and efficiently invertible using a secret trapdoor. This notion has been used to obtain advanced constructions of signatures with strong guarantees against leakage and tampering, and also by Dodis, Vaikunthanathan, and Wichs (EUROCRYPT'20) to obtain constructions of randomness extractors with extractor-dependent sources. While these applications are motivated by practical considerations, the only known instantiation of CALBO-TDFs so far relies on the existence of indistinguishability obfuscation. In this paper, we propose the first two instantiations of CALBO-TDFs based on standard assumptions. Our constructions are based on the LWE assumption with a sub-exponential approximation factor and on the DCR assumption, respectively, and circumvent the use of indistinguishability obfuscation by relying on lossy modes and trapdoor mechanisms enabled by these assumptions.

Note: This is the full version of a publication at SCN 2022.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. SCN 2022
Lossy trapdoor functions cumulative lossiness standard assumptions
Contact author(s)
benoit libert @ ens-lyon fr
ky nguyen @ ens fr
alain passelegue @ inria fr
2022-09-16: approved
2022-09-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benoît Libert and Ky Nguyen and Alain Passelègue},
      title = {Cumulatively All-Lossy-But-One Trapdoor Functions from Standard Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1229},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.