International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

New Techniques for Efficient Trapdoor Functions and Applications

Authors:
Sanjam Garg
Romain Gay
Mohammad Hajiabadi
Download:
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
BibTeX
@article{eurocrypt-2019-29380,
  title={New Techniques for Efficient Trapdoor Functions and Applications},
  booktitle={Advances in Cryptology – EUROCRYPT 2019},
  series={Advances in Cryptology – EUROCRYPT 2019},
  publisher={Springer},
  volume={11478},
  pages={33-63},
  doi={10.1007/978-3-030-17659-4_2},
  author={Sanjam Garg and Romain Gay and Mohammad Hajiabadi},
  year=2019
}