International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: New Techniques for Efficient Trapdoor Functions and Applications

Sanjam Garg
Romain Gay
Mohammad Hajiabadi
DOI: 10.1007/978-3-030-17659-4_2 (login may be required)
Search ePrint
Search Google
Abstract: 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 obtainThe 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.
Video from EUROCRYPT 2019
  title={New Techniques for Efficient Trapdoor Functions and Applications},
  booktitle={Advances in Cryptology – EUROCRYPT 2019},
  series={Advances in Cryptology – EUROCRYPT 2019},
  author={Sanjam Garg and Romain Gay and Mohammad Hajiabadi},