26/07/2019, 16:00 — 17:00 — Room P4.35, Mathematics Building
Nico Döttling, Helmholtz Center for Information Security (CISPA)
Trapdoor Hash Functions and their Applications
We introduce a new primitive, called trapdoor hash functions (TDH), which are compressing hash functions with additional trapdoor function-like properties. Specifically, given an index $i$, TDHs allow for sampling an encoding key $e_k$ (which hides $i$) along with a corresponding trapdoor. Furthermore, given a hash value $H(x)$, a hint value $E(e_k,x)$, and the trapdoor corresponding to $e_k$, 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(e_k,x)$ be? We obtain constructions where the hint is only one bit long based on DDH, QR, DCR, or LWE.
As the main application, we obtain the first constructions of private information retrieval (PIR) protocols with communication cost poly-logarithmic in the database size based on DDH or QR. These protocols are in fact rate-1 when considering block PIR.
