Paper 2019/639
Trapdoor Hash Functions and Their Applications
Nico Döttling, Sanjam Garg, Yuval Ishai, Giulio Malavolta, Tamer Mour, and Rafail Ostrovsky
Abstract
We introduce a new primitive, called trapdoor hash functions (TDH), which are hash functions $H: \{0,1\}^n \rightarrow \{0,1\}^\textrm{sec}$ with additional trapdoor functionlike properties. Specifically, given an index $i\in[n]$, TDHs allow for sampling an encoding key $\textrm{ek}$ (that hides $i$) along with a corresponding trapdoor. Furthermore, given $\mathsf{H}(x)$, a hint value $\mathsf{E}(\textrm{ek},x)$, and the trapdoor corresponding to $\textrm{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 $\mathsf{E}(\textrm{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 lowcommunication secure computation. We mainly focus on twomessage 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 (twomessage) rate1 string OT based on DDH, QR, or LWE. This has several useful consequences, such as: (a) The first constructions of PIR with communication cost polylogarithmic in the database size based on DDH or QR. These protocols are in fact rate1 when considering block PIR. (b) The first constructions of a semicompact 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 constantrate LWEbased construction of a 2message ``statistically senderprivate'' OT protocol in the plain model. 2. The first rate1 protocols (under any assumption) for $n$ parallel OTs and matrixvector products from DDH, QR or LWE. We further consider the setting where $f$ evaluates a RAM program $y$ with running time $T\ll x$ on $x$. We obtain the first protocols with communication sublinear in the size of $x$, namely $T\cdot\sqrt{x}$ or $T\cdot\sqrt[3]{x}$, based on DDH or, resp., pairings (and correlatedinput secure hash functions).
Metadata
 Available format(s)
 Publication info
 A major revision of an IACR publication in CRYPTO 2019
 Contact author(s)

tamer @ weizmann ac il
giulio malavolta @ hotmail it
rafail @ cs ucla edu
sanjamg @ berkeley edu
nico doettling @ gmail com
yuvali @ cs technion ac il  History
 20190603: last of 2 revisions
 20190603: received
 See all versions
 Short URL
 https://ia.cr/2019/639
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/639, author = {Nico Döttling and Sanjam Garg and Yuval Ishai and Giulio Malavolta and Tamer Mour and Rafail Ostrovsky}, title = {Trapdoor Hash Functions and Their Applications}, howpublished = {Cryptology ePrint Archive, Paper 2019/639}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/639}}, url = {https://eprint.iacr.org/2019/639} }