International Association
for Cryptologic Research

We put forth the problem of delegating the evaluation of a

pseudorandom function (PRF) to an untrusted proxy. A {\\em delegatable PRF}, or DPRF for short, is a new primitive that enables a proxy to evaluate a PRF on a strict subset of its domain using a trapdoor derived from the DPRF secret-key. PRF delegation is

\\emph{policy-based}: the trapdoor is constructed with respect to a

certain policy that determines the subset of input values which the

proxy is allowed to compute. Interesting DPRFs should achieve

\\emph{low-bandwidth delegation}: Enabling the proxy to compute the PRF values that conform to the policy should be more efficient than simply providing the proxy with the sequence of all such values precomputed.

The main challenge in constructing DPRFs is in maintaining the

pseudorandomness of unknown values in the face of an attacker that

adaptively controls proxy servers. A DPRF may be optionally equipped

with an additional property we call \\emph{policy privacy}, where any

two delegation predicates remain indistinguishable in the view of a

DPRF-querying proxy: Achieving this raises new design challenges as

policy privacy and efficiency are seemingly conflicting goals.

For the important class of policies described as (1-dimensional)

\\emph{ranges}, we devise two DPRF constructions and rigorously prove

their security. Built upon the well-known tree-based GGM PRF

family~\\cite{GGM86}, our constructions are generic and feature only

logarithmic delegation size in the number of values conforming to the

policy predicate. At only a constant-factor efficiency reduction, we

show that our second construction is also policy private. As we

finally describe, their new security and efficiency properties render

our delegated PRF schemes particularly useful in numerous security

applications, including RFID, symmetric searchable encryption, and

broadcast encryption.