TAA Research LunchDate: 18 June 2025
Time: 11:45 – 12:45
Location: Forschungslabor 3 (sofa room)
Speaker: Karen Azari
Title: On the Provable Security of Prefix-constrained Pseudorandom Functions
Abstract:
In the field of cryptography, we propose protocols that provide strong provable security guarantees, that is, one can mathematically prove that attacks against the scheme are impossible, or at least as hard to achieve as solving a computational problem that mathematicians failed to solve despite extensive research. When analyzing a more involved scheme that is based on several simpler cryptographic primitives, we prove that any attack against the scheme implies an attack against one of the underlying building blocks, where security of the building blocks in turn is based on mathematical hardness assumptions. In this talk, I will discuss the difficulty of proving security of so-called constrained pseudorandom functions (CPRFs).
A CPRF is a PRF with the following additional functionality: Given the secret key and a constraint, one can generate a constrained key which allows to evaluate the PRF on all inputs satisfying the constraint. For security, one requires that the function output on inputs not satisfying the constraint should remain pseudorandom. A prominent example of a CPRF is the construction of Goldreich, Goldwasser and Micali [GGM84], which supports prefix constraints and is based on pseudorandom generators. While selective security, where the adversary has to commit to its choices in the beginning of the security experiment, is relatively easy to prove for the GGM CPRF, it remained open for a long time to prove the stronger notion of adaptive security, where the adversary is allowed to make its choices on-the-fly, depending on what they learn during the game. I will discuss the difficulty of proving adaptive security of the GGM PRF and provide a brief intuition on how we could finally solve the problem using a new rewinding proof technique.
