File(s) not publicly available

Trapdoor Hash Functions and Their Applications

conference contribution
posted on 2023-11-29, 18:10 authored by Nico DöttlingNico Döttling, Sanjam Garg, Yuval Ishai, Giulio Malavolta, Tamer Mour, Rafail Ostrovsky

We introduce a new primitive, called trapdoor hash functions (TDH), which are hash functions H : {0, 1}
n → {0, 1} λ with additional trapdoor function-like properties. Specifically, given an index i ∈ [n], TDHs allow for sampling an encoding key ek (that hides i) along with a corresponding trapdoor. Furthermore, given H(x), a hint value E(ek, x), and the trapdoor corresponding to ek, the i th bit of x can be efficiently recovered. In this setting, one of our main questions is: How small can the hint value E(ek, x) be? We obtain constructions where the hint is only one bit long based on DDH, QR, DCR, or LWE.
This primitive opens a floodgate of applications for low-communication secure computation. We mainly focus on two-message protocols between a receiver and a sender, with private inputs x and y, resp., where the receiver should learn f(x, y). We wish to optimize the (download) rate of such protocols, namely the asymptotic ratio between the size of the output and the sender’s message. Using TDHs, we obtain:
1. The first protocols for (two-message) rate-1 string OT based on DDH, QR, or LWE. This has several useful consequences, such as:
(a) The first constructions of PIR with communication cost poly-logarithmic in the database size based on DDH or QR. These protocols are in fact rate-1 when considering block
(b) The first constructions of a semi-compact homomorphic encryption scheme for branching programs, where the encrypted output grows only with the program length, based on DDH or QR.
(c) The first constructions of lossy trapdoor functions with input to output ratio approaching 1 based on DDH, QR or LWE.
(d) The first constant-rate LWE-based construction of a 2-message “statistically senderprivate” OT protocol in the plain model.
2. The first rate-1 protocols (under any assumption) for n parallel OTs and matrix-vector products from DDH, QR or LWE. We further consider the setting where f evaluates a RAM program y with running time T |x| on x. We obtain the first protocols with communication sublinear in the size of x, namely T · p |x| or T · p3 |x|, based on DDH or, resp., pairings (and correlated-input secure hash functions).


Preferred Citation

Nico Döttling, Sanjam Garg, Yuval Ishai, Giulio Malavolta, Tamer Mour and Rafail Ostrovsky. Trapdoor Hash Functions and Their Applications. In: Advances in Cryptology (CRYPTO). 2019.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

Advances in Cryptology (CRYPTO)

Legacy Posted Date


Open Access Type

  • Unknown


@inproceedings{cispa_all_2923, title = "Trapdoor Hash Functions and Their Applications", author = "Döttling, Nico and Garg, Sanjam and Ishai, Yuval and Malavolta, Giulio and Mour, Tamer and Ostrovsky, Rafail", booktitle="{Advances in Cryptology (CRYPTO)}", year="2019", }

Usage metrics


    No categories selected


    Ref. manager