How to Build a Trapdoor Function from an Encryption Scheme

Sanjam Garg, Mohammad Hajiabadi, Giulio Malavolta, Rafail Ostrovsky

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


In this work we ask the following question: Can we transform any encryption scheme into a trapdoor function (TDF)? Alternatively stated, can we make any encryption scheme randomness recoverable? We propose a generic compiler that takes as input any encryption scheme with pseudorandom ciphertexts and adds a trapdoor to invert the encryption, recovering also the random coins. This universal TDFier only assumes in addition the existence of a hinting pseudorandom generator (PRG). Despite the simplicity, our transformation is quite general and we establish a series of new feasibility results: The first identity-based TDF [Bellare et al. EUROCRYPT 2012] from the CDH assumption in pairing-free groups (or from factoring), thus matching the state of the art for identity-based encryption schemes. Prior works required pairings or LWE.The first collusion-resistant attribute-based TDF (AB-TDF) for all (NC1, resp.) circuits from LWE (bilinear maps, resp.). Moreover, the first single-key AB-TDF from CDH. To the best of our knowledge, no AB-TDF was known in the literature (not even for a single key) from any assumption. We obtain the same results for predicate encryption. As an additional contribution, we define and construct a trapdoor garbling scheme: A simulation secure garbling scheme with a hidden “trigger” that allows the evaluator to fully recover the randomness used by the garbling algorithm. We show how to construct trapdoor garbling from the DDH or LWE assumption with an interplay of key-dependent message (KDM) and randomness-dependent message (RDM) techniques. Trapdoor garbling allows us to obtain alternative constructions of (single-key) AB-TDFs with additional desirable properties, such as adaptive security (in the choice of the attribute) and projective keys. We expect trapdoor garbling to be useful in other contexts, e.g. in case where, upon successful execution, the evaluator needs to immediately verify that the garbled circuit was well-formed.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part 3
EditorsMehdi Tibouchi, Huaxiong Wang
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages30
ISBN (Print)9783030920777
StatePublished - 2021
Event27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021 - Virtual, Online
Duration: Dec 6 2021Dec 10 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13092 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021
CityVirtual, Online

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'How to Build a Trapdoor Function from an Encryption Scheme'. Together they form a unique fingerprint.

Cite this