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.

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

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},
note = {\url{https://eprint.iacr.org/2017/477}},
url = {https://eprint.iacr.org/2017/477}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.