Paper 2018/872

New Techniques for Efficient Trapdoor Functions and Applications

Sanjam Garg, Romain Gay, and Mohammad Hajiabadi


We develop techniques for constructing trapdoor functions (TDFs) with short image size and advanced security properties. Our approach builds on the recent framework of Garg and Hajiabadi [CRYPTO 2018]. As applications of our techniques, we obtain -- The first construction of deterministic-encryption schemes for block-source inputs (both for the CPA and CCA cases) based on the Computational Diffie-Hellman (CDH) assumption. Moreover, by applying our efficiency-enhancing techniques, we obtain CDH-based schemes with ciphertext size linear in plaintext size. -- The first construction of lossy TDFs based on the Decisional Diffie-Hellman (DDH) assumption with image size linear in input size, while retaining the lossiness rate of [Peikert-Waters STOC 2008]. Prior to our work, all constructions of deterministic encryption based even on the stronger DDH assumption incurred a quadratic gap between the ciphertext and plaintext sizes. Moreover, all DDH-based constructions of lossy TDFs had image size quadratic in the input size. At a high level, we break the previous quadratic barriers by introducing a novel technique for encoding input bits via hardcore output bits with the use of erasure-resilient codes. All previous schemes used group elements for encoding input bits, resulting in quadratic expansions.

Note: Fixed an issue with the definition of balanced predicates (Definition 6.2).

Available format(s)
Publication info
A minor revision of an IACR publication in EUROCRYPT 2019
Trapdoor functionsLossy trapdoor functionsComputational Diffie-Hellman assumption
Contact author(s)
mdhajiabadi @ berkeley edu
2019-05-23: last of 7 revisions
2018-09-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sanjam Garg and Romain Gay and Mohammad Hajiabadi},
      title = {New Techniques for Efficient Trapdoor Functions and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2018/872},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.