Cryptology ePrint Archive: Report 2017/477

Constrained Keys for Invertible Pseudorandom Functions

Dan Boneh and 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 are impossible under our definition.

Category / Keywords: secret-key cryptography / pseudorandom functions (PRFs), invertible PRFs, constrained PRFs

Date: received 28 May 2017

Contact author: dwu4 at cs stanford edu

Available format(s): PDF | BibTeX Citation

Version: 20170529:163426 (All versions of this report)

Short URL: ia.cr/2017/477

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]