Key Homomorphic PRFs and Their Applications

A pseudorandom function

$F: {\mathcal K} \times{\mathcal X} \to{\mathcal Y}$

is said to be key homomorphic if given

F

(

k

1

,

x

) and

F

(

k

2

,

x

) there is an efficient algorithm to compute

F

(

k

1

 ⊕ 

k

2

,

x

), where ⊕ denotes a group operation on

k

1

and

k

2

such as

xor

. Key homomorphic PRFs are natural objects to study and have a number of interesting applications: they can simplify the process of rotating encryption keys for encrypted data stored in the cloud, they give one round distributed PRFs, and they can be the basis of a symmetric-key proxy re-encryption scheme. Until now all known constructions for key homomorphic PRFs were only proven secure in the random oracle model. We construct the first provably secure key homomorphic PRFs in the standard model. Our main construction is based on the learning with errors (LWE) problem. We also give a construction based on the decision linear assumption in groups with an ℓ-linear map. We leave as an open problem the question of constructing standard model key homomorphic PRFs from more general assumptions.