Delegatable pseudorandom functions and applications

Aggelos Kiayias, Stavros Papadopoulos, Nikos Triandopoulos, Thomas Zacharias

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

243 Scopus citations

Abstract

We put forth the problem of delegating the evaluation of a pseudorandom function (PRF) to an untrusted proxy and introduce a novel cryptographic primitive called delegatable pseudorandom functions, or DPRFs for short: A DPRF enables a proxy to evaluate a pseudorandom function on a strict subset of its domain using a trapdoor derived from the DPRF secret key. The trapdoor is constructed with respect to a certain policy predicate that determines the subset of input values which the proxy is allowed to compute. The main challenge in constructing DPRFs is to achieve bandwidth efficiency (which mandates that the trapdoor is smaller than the precomputed sequence of the PRF values conforming to the predicate), while maintaining the pseudorandomness of unknown values against an attacker that adaptively controls the proxy. A DPRF may be optionally equipped with an additional property we call 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 bandwidth efficiency are seemingly conflicting goals. For the important class of policy predicates described as (1-dimensional) ranges, we devise two DPRF constructions and rigorously prove their security. Built upon the well-known tree-based GGM PRF family, 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. Finally, we describe that their new security and efficiency properties render our DPRF schemes particularly useful in numerous security applications, including RFID, symmetric searchable encryption, and broadcast encryption.

Original languageEnglish
Title of host publicationCCS 2013 - Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security
Pages669-683
Number of pages15
DOIs
StatePublished - 2013
Event2013 ACM SIGSAC Conference on Computer and Communications Security, CCS 2013 - Berlin, Germany
Duration: 4 Nov 20138 Nov 2013

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221

Conference

Conference2013 ACM SIGSAC Conference on Computer and Communications Security, CCS 2013
Country/TerritoryGermany
CityBerlin
Period4/11/138/11/13

Keywords

  • authentication
  • broadcast encryption
  • delegation of computation
  • pseudorandom functions
  • rfids
  • searchable encryption

Fingerprint

Dive into the research topics of 'Delegatable pseudorandom functions and applications'. Together they form a unique fingerprint.

Cite this