Key-homomorphic constrained pseudorandom functions

Banerjee A, Fuchsbauer G, Peikert C, Pietrzak KZ, Stevens S. 2015. Key-homomorphic constrained pseudorandom functions. 9015, 31–60.

OA IST-2016-679-v1+1_180.pdf 450.67 KB

Conference Paper | Published | English

Scopus indexed
Banerjee, Abishek; Fuchsbauer, GeorgIST Austria; Peikert, Chris; Pietrzak, Krzysztof ZIST Austria ; Stevens, Sophie
Series Title
A pseudorandom function (PRF) is a keyed function F : K × X → Y where, for a random key k ∈ K, the function F(k, ·) is indistinguishable from a uniformly random function, given black-box access. A key-homomorphic PRF has the additional feature that for any keys k, k' and any input x, we have F(k+k', x) = F(k, x)⊕F(k', x) for some group operations +,⊕ on K and Y, respectively. A constrained PRF for a family of setsS ⊆ P(X) has the property that, given any key k and set S ∈ S, one can efficiently compute a “constrained” key kS that enables evaluation of F(k, x) on all inputs x ∈ S, while the values F(k, x) for x /∈ S remain pseudorandom even given kS. In this paper we construct PRFs that are simultaneously constrained and key homomorphic, where the homomorphic property holds even for constrained keys. We first show that the multilinear map-based bit-fixing and circuit-constrained PRFs of Boneh and Waters (Asiacrypt 2013) can be modified to also be keyhomomorphic. We then show that the LWE-based key-homomorphic PRFs of Banerjee and Peikert (Crypto 2014) are essentially already prefix-constrained PRFs, using a (non-obvious) definition of constrained keys and associated group operation. Moreover, the constrained keys themselves are pseudorandom, and the constraining and evaluation functions can all be computed in low depth. As an application of key-homomorphic constrained PRFs,we construct a proxy re-encryption schemewith fine-grained access control. This scheme allows storing encrypted data on an untrusted server, where each file can be encrypted relative to some attributes, so that only parties whose constrained keys match the attributes can decrypt. Moreover, the server can re-key (arbitrary subsets of) the ciphertexts without learning anything about the plaintexts, thus permitting efficient and finegrained revocation.
Publishing Year
Date Published
31 - 60
TCC: Theory of Cryptography Conference
Conference Location
Warsaw, Poland
Conference Date
2015-03-23 – 2015-03-25

Cite this

Banerjee A, Fuchsbauer G, Peikert C, Pietrzak KZ, Stevens S. Key-homomorphic constrained pseudorandom functions. 2015;9015:31-60. doi:10.1007/978-3-662-46497-7_2
Banerjee, A., Fuchsbauer, G., Peikert, C., Pietrzak, K. Z., & Stevens, S. (2015). Key-homomorphic constrained pseudorandom functions. Presented at the TCC: Theory of Cryptography Conference, Warsaw, Poland: Springer.
Banerjee, Abishek, Georg Fuchsbauer, Chris Peikert, Krzysztof Z Pietrzak, and Sophie Stevens. “Key-Homomorphic Constrained Pseudorandom Functions.” Lecture Notes in Computer Science. Springer, 2015.
A. Banerjee, G. Fuchsbauer, C. Peikert, K. Z. Pietrzak, and S. Stevens, “Key-homomorphic constrained pseudorandom functions,” vol. 9015. Springer, pp. 31–60, 2015.
Banerjee A, Fuchsbauer G, Peikert C, Pietrzak KZ, Stevens S. 2015. Key-homomorphic constrained pseudorandom functions. 9015, 31–60.
Banerjee, Abishek, et al. Key-Homomorphic Constrained Pseudorandom Functions. Vol. 9015, Springer, 2015, pp. 31–60, doi:10.1007/978-3-662-46497-7_2.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
MD5 Checksum


Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar