International Association
for Cryptologic Research

We put forward a new notion of pseudorandom functions (PRFs) we call

constrained PRFs. In a standard PRF there is a master key k that enables one to evaluate the function at all points in the domain of the

function. In a constrained PRF it is possible to derive constrained keys kS from the master key k. A constrained key kS enables the

evaluation of the PRF at a certain subset S of the domain and

nowhere else. We present a formal framework for this concept and show

that constrained PRFs can be used to construct powerful primitives such as identity-based key exchange and an optimal private broadcast

encryption system. We then construct constrained PRFs for several natural set systems needed for these applications. We conclude with several open problems relating to this new concept.