Constraining Pseudorandom Functions Privately
David Wu, Stanford University
May 10, 2016 2:00pm, in DC 2585
In a constrained pseudorandom function (PRF), the holder of the master secret key is able to derive constrained keys with respect to a boolean circuit C. The constrained key can be used to evaluate the PRF on all inputs x for which C(x) = 1. In almost all existing constructions of constrained PRFs, the constrained key itself reveals its underlying constraints. We introduce the concept of private constrained PRFs, which are constrained PRFs with the additional property that the constrained keys do not reveal their constraints. Our main notion of privacy captures the intuition that an adversary, given a constrained key for one of two circuits, is unable to tell which circuit is associated with its key. As a primitive, private constrained PRFs have many natural applications in searchable symmetric encryption, deniable encryption, and more. In this talk, I will introduce our notion of privacy for private constrained PRFs, and describe some of their applications. Finally, I will show how we can construct private constrained PRFs for different classes of constraints using indistinguishability obfuscation or concrete assumptions on multilinear maps.
Joint work with Dan Boneh and Kevin Lewi
David Wu is a third-year PhD student in the Department of Computer Science at Stanford University, advised by Dan Boneh. He works on a mix of problems in applied and theoretical cryptography. On the applied side, his work has primarily focused on developing new cryptographic protocols for different privacy-preserving applications, such as database queries, machine learning, and navigation. On the theoretical side, he has worked on constructing new cryptographic primitives from multilinear maps, as well as on several problems related to functional encryption. David is the recipient of an NSF Graduate Research Fellowship.