Paper 2013/379

Delegatable Pseudorandom Functions and Applications

Aggelos Kiayias, Stavros Papadopoulos, Nikos Triandopoulos, and Thomas Zacharias


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.

Available format(s)
Publication info
Published elsewhere. Minor revision. ACM CCS 2013
Contact author(s)
th_zach @ otenet gr
2013-08-20: revised
2013-06-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aggelos Kiayias and Stavros Papadopoulos and Nikos Triandopoulos and Thomas Zacharias},
      title = {Delegatable Pseudorandom Functions and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2013/379},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.