Constraining Pseudorandom Functions Privately

In a constrained pseudorandom function PRF, the master secret key can be used to derive constrained keys, where each constrained keyi¾?k is constrained with respect to some Boolean circuiti¾?C. A constrained keyi¾?k can be used to evaluate the PRF on all inputsi¾?x for which $$Cx = 1$$. In almost all existing constrained PRF constructions, the constrained keyi¾?k reveals its constrainti¾?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 keyi¾?k for one of two circuits $$C_0$$ and $$C_1$$, is unable to tell which circuit is associated with the keyi¾?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.