CROSSING Research Seminar

Organizer: Jacqueline Brendel, CROSSING

Abstract

We study security of *compiled* pseudo-random functions (PRFs):

Evaluating a PRF in a multi-party protocol gives oblivious PRFs and ultimately private set-intersection, while function secret-sharing a PRF leads to pseudo-*correlated*-functions. Normal PRFs are usually considered to be quite efficient in practice, however to make use of *compiled* PRFs efficient we usually rely on *weak* PRFs (which are only secure on *random* inputs and, in contrast to normal PRFs, can plausibly be realized by low-depth circuits). To recover security for arbitrary inputs, a hash function -- modeled as a random oracle -- can be used to pre-process the inputs and recover security.

While random oracles do not exist in general, for specific applications like this there is hope to achieve provable security. In our work, we give a concrete hash function -- a composition of an extremely lossy function (ELF) together with a PRF is *public* key -- which, together with a slight strengthening of the notion of weak PRFs, allows proving security of the composition thus justifying the construction strategy. While primarily a foundational study the construction would be efficient enough for practical use. We further justify the strengthened notion of pseudorandom-input weak-PRFs (PI-PRF) by (a) extending the security analysis of candidate weak PRFs like BIPSW18 and show it plausibly achieves the stronger notion under the same arguments and (b) adapting an argument by Pietrzak and Sjödin showing that any separating example directly implies key agreement.

One aspect I want to highlight in this talk is the use of a PRF where the key is publicly known to achieve security properties as well as the new notion of PI-PRFs and its justification. In addition I plan to cover our ELF based proof strategy which we also applied to (a variant of) the Fujisaki-Otamoto transform.

Speaker Bio

Christoph Egger is a Marie Skłodowska-Curie Fellow at the Institut de Recherche en Informatique Fondamentale in Paris, France hosted by Geoffroy Couteau. After finishing their doctoral studies in Erlangen which focused on proof techniques for key exchange protocols, and privacy measures for anonymous systems, Christoph is now focusing on cryptography in the fine-grained and bounded-space setting and enjoys working with non black-box techniques like extremely lossy functions.