Cryptology ePrint Archive: Report 2015/1167

Constraining Pseudorandom Functions Privately

Dan Boneh and Kevin Lewi and David J. Wu

Abstract: In a constrained pseudorandom function (PRF), the master secret key can be used to derive constrained keys, where each constrained key k is constrained with respect to some Boolean circuit C. A constrained key k can be used to evaluate the PRF on all inputs x for which C(x) = 1. In almost all existing constrained PRF constructions, the constrained key k reveals its constraint C.

In this paper we introduce the concept of private constrained PRFs, which are constrained PRFs with the additional property that a constrained key does not reveal its constraint. Our main notion of privacy captures the intuition that an adversary, given a constrained key k for one of two circuits C_0 and C_1, is unable to tell which circuit is associated with the key k. We show that constrained PRFs have natural applications to searchable symmetric encryption, cryptographic watermarking, and much more.

To construct private constrained PRFs we first demonstrate that our strongest notions of privacy and functionality can be achieved using indistinguishability obfuscation. Then, for our main constructions, we build private constrained PRFs for bit-fixing constraints and for puncturing constraints from concrete algebraic assumptions.

Category / Keywords: secret-key cryptography / pseudorandom functions, multilinear maps, indistinguishability obfuscation

Original Publication (with major differences): IACR-PKC-2017

Date: received 3 Dec 2015, last revised 26 Feb 2017

Contact author: klewi at cs stanford edu

Available format(s): PDF | BibTeX Citation

Version: 20170227:042252 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]