Cryptography, Security, and Privacy (CrySP)

This speaker series is made possible by an anonymous charitable donation in memory of cypherpunks and privacy advocates Len Sassaman, Hugh Daniel, Hal Finney, and Caspar Bowden.

View the list of past and upcoming speakers

Constraining Pseudorandom Functions Privately

David Wu, Stanford University

[Download (MP4)] [View on Youtube]

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.