TY - GEN
T1 - Delegatable pseudorandom functions and applications
AU - Kiayias, Aggelos
AU - Papadopoulos, Stavros
AU - Triandopoulos, Nikos
AU - Zacharias, Thomas
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
KW - authentication
KW - broadcast encryption
KW - delegation of computation
KW - pseudorandom functions
KW - rfids
KW - searchable encryption
UR - http://www.scopus.com/inward/record.url?scp=84889072826&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84889072826&partnerID=8YFLogxK
U2 - 10.1145/2508859.2516668
DO - 10.1145/2508859.2516668
M3 - Conference contribution
AN - SCOPUS:84889072826
SN - 9781450324779
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 669
EP - 683
BT - CCS 2013 - Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security
T2 - 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS 2013
Y2 - 4 November 2013 through 8 November 2013
ER -