Paper 2015/1167

Constraining Pseudorandom Functions Privately

Dan Boneh, Kevin Lewi, and David J. Wu


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.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in PKC 2017
pseudorandom functionsmultilinear mapsindistinguishability obfuscation
Contact author(s)
klewi @ cs stanford edu
2017-02-27: last of 3 revisions
2015-12-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dan Boneh and Kevin Lewi and David J.  Wu},
      title = {Constraining Pseudorandom Functions Privately},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1167},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.