Cryptology ePrint Archive: Report 2018/872

New Techniques for Efficient Trapdoor Functions and Applications

Sanjam Garg and Romain Gay and Mohammad Hajiabadi

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 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.

Category / Keywords: Trapdoor functions, Lossy trapdoor functions, Computational Diffie-Hellman assumption

Date: received 17 Sep 2018, last revised 4 Oct 2018

Contact author: mdhajiabadi at berkeley edu

Available format(s): PDF | BibTeX Citation

Note: Updated the multiplicative constants required in error correction. Also, fixed typos.

Version: 20181004:165339 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]