Abstract. 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 ek (which hides i) along with a corresponding trapdoor. Furthermore, given a hash value 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. 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.
Biography. I am a tenure-track faculty at the Helmholtz Center for Information Security (CISPA) in Saarbrücken. The focus of my research is public key encryption and secure two-party computation. From 2017 to 2018 I was assistant professor at the Friedrich-Alexander-University Erlangen Nürnberg. Prior to that, I was a postdoc in the group of Sanjam Garg at UC Berkeley, supported by a DAAD fellowship from 2016 to 2017 and a postdoc in the crypto group of Aarhus University, working with Ivan Damgård and Jesper Buus Nielsen form 2014 to 2016. I finished my PhD in 2014 at the Karlsruhe Institute of Technology under the supervision of Jörn Müller-Quade. I am the 2014 winner of the biennial Erika and Dr. Wolfgang Eichelberger Dissertation Award.
