[Busec] Seminar Wednesday Nov 8: Constrained Keys for Invertible Pseudorandom Functions

Yilei Chen chenyl at bu.edu
Mon Nov 6 13:43:55 EST 2017

Title: Constrained Keys for Invertible Pseudorandom Functions
Speaker: David Wu (Stanford)
Wednesday Nov 8, 2017, 10 am - 11 am.
BU Hariri Institute Seminar room. 111 Cummington St, Boston MA 02215.
Lunch at BUsec lounge after the talk.

A constrained pseudorandom function (PRF) is a secure PRF for which one can
generate constrained keys that can only be used to evaluate the PRF on a
subset of the domain. Constrained PRFs are widely used in cryptography,
most notably in applications of indistinguishability obfuscation (iO). A
natural question then is whether we can constrain other cryptographic
primitives, such as pseudorandom permutations (PRPs).

In this talk, I will first show that constraining PRPs is much more
difficult than constraining PRFs, and in fact, for many natural classes of
constraints, constrained PRPs do not exist. I will then introduce the
notion of an invertible PRF (IPF), which can be viewed as an intermediate
notion between PRFs and PRPs. Specifically, an IPF is a secure injective
PRF accompanied by an efficient inversion algorithm. A constrained key for
an IPF can only be used to evaluate the IPF on a subset S of the domain,
and to invert the IPF on the image of S. I will conclude the talk by giving
two constructions of constrained IPFs from standard lattice assumptions:
one for the class of puncturing constraints and another for general circuit
constraints. Both of our constructions rely heavily on recent work on
constructing private constrained PRFs.

Joint work with Dan Boneh and Sam Kim
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20171106/9839cf14/attachment.html>

More information about the Busec mailing list