International Association
for Cryptologic Research

In a constrained pseudorandom function (PRF), the holder of the master secret key can derive constrained keys with respect to a boolean circuit C. The constrained key can be used to evaluate the PRF on all inputs x for which C(x) = 1. In almost all existing constructions of constrained PRFs, the constrained key itself reveals its constraints. We introduce the concept of private constrained PRFs, which are constrained PRFs with the additional property that the constrained keys do not reveal their constraints. Our main notion of privacy captures the intuition that an adversary, given a constrained key for one of two circuits $C_0$ and $C_1$, is unable to tell which circuit is associated with its key. As a primitive, private constrained PRFs have many natural applications in searchable symmetric encryption, deniable encryption, and more.

We then show how to instantiate private constrained PRFs. Our first construction uses indistinguishability obfuscation and achieves our strongest notions of functionality and privacy. We also give two constructions based on concrete assumptions on multilinear maps which achieve slightly weaker notions of privacy and for more limited classes of constraints: namely, for the class of bit-fixing constraints and puncturing constraints.