Constrained Keys for Invertible Pseudorandom Functions

Dan Boneh; Sam Kim; David J.  Wu

Paper 2017/477

Constrained Keys for Invertible Pseudorandom Functions

Dan Boneh, Sam Kim, and David J. Wu

Abstract

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 used widely, most notably in applications of indistinguishability obfuscation (iO). In this paper we show how to constrain an invertible PRF (IPF), which is significantly harder. An IPF is a secure injective PRF accompanied by an 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. We first define the notion of a constrained IPF and then give two main constructions: one for puncturing an IPF and the other for (single-key) circuit constraints. Both constructions rely on recent work on private constrained PRFs. We also show that constrained pseudorandom permutations for many classes of constraints are impossible under our definition.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: A major revision of an IACR publication in TCC 2017
Keywords: pseudorandom functions (PRFs)invertible PRFs constrained PRFs
Contact author(s): dwu4 @ cs stanford edu
History: 2017-09-22: revised; 2017-05-29: received; See all versions
Short URL: https://ia.cr/2017/477
License: CC BY

BibTeX

@misc{cryptoeprint:2017/477,
      author = {Dan Boneh and Sam Kim and David J.  Wu},
      title = {Constrained Keys for Invertible Pseudorandom Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/477},
      year = {2017},
      url = {https://eprint.iacr.org/2017/477}
}