---
_id: '1646'
abstract:
- lang: eng
  text: '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.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Abishek
  full_name: Banerjee, Abishek
  last_name: Banerjee
- first_name: Georg
  full_name: Fuchsbauer, Georg
  id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
  last_name: Fuchsbauer
- first_name: Chris
  full_name: Peikert, Chris
  last_name: Peikert
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
- first_name: Sophie
  full_name: Stevens, Sophie
  last_name: Stevens
citation:
  ama: 'Banerjee A, Fuchsbauer G, Peikert C, Pietrzak KZ, Stevens S. Key-homomorphic
    constrained pseudorandom functions. In: <i>12th Theory of Cryptography Conference</i>.
    Vol 9015. Springer Nature; 2015:31-60. doi:<a href="https://doi.org/10.1007/978-3-662-46497-7_2">10.1007/978-3-662-46497-7_2</a>'
  apa: 'Banerjee, A., Fuchsbauer, G., Peikert, C., Pietrzak, K. Z., &#38; Stevens,
    S. (2015). Key-homomorphic constrained pseudorandom functions. In <i>12th Theory
    of Cryptography Conference</i> (Vol. 9015, pp. 31–60). Warsaw, Poland: Springer
    Nature. <a href="https://doi.org/10.1007/978-3-662-46497-7_2">https://doi.org/10.1007/978-3-662-46497-7_2</a>'
  chicago: Banerjee, Abishek, Georg Fuchsbauer, Chris Peikert, Krzysztof Z Pietrzak,
    and Sophie Stevens. “Key-Homomorphic Constrained Pseudorandom Functions.” In <i>12th
    Theory of Cryptography Conference</i>, 9015:31–60. Springer Nature, 2015. <a href="https://doi.org/10.1007/978-3-662-46497-7_2">https://doi.org/10.1007/978-3-662-46497-7_2</a>.
  ieee: A. Banerjee, G. Fuchsbauer, C. Peikert, K. Z. Pietrzak, and S. Stevens, “Key-homomorphic
    constrained pseudorandom functions,” in <i>12th Theory of Cryptography Conference</i>,
    Warsaw, Poland, 2015, vol. 9015, pp. 31–60.
  ista: 'Banerjee A, Fuchsbauer G, Peikert C, Pietrzak KZ, Stevens S. 2015. Key-homomorphic
    constrained pseudorandom functions. 12th Theory of Cryptography Conference. TCC:
    Theory of Cryptography Conference, LNCS, vol. 9015, 31–60.'
  mla: Banerjee, Abishek, et al. “Key-Homomorphic Constrained Pseudorandom Functions.”
    <i>12th Theory of Cryptography Conference</i>, vol. 9015, Springer Nature, 2015,
    pp. 31–60, doi:<a href="https://doi.org/10.1007/978-3-662-46497-7_2">10.1007/978-3-662-46497-7_2</a>.
  short: A. Banerjee, G. Fuchsbauer, C. Peikert, K.Z. Pietrzak, S. Stevens, in:, 12th
    Theory of Cryptography Conference, Springer Nature, 2015, pp. 31–60.
conference:
  end_date: 2015-03-25
  location: Warsaw, Poland
  name: 'TCC: Theory of Cryptography Conference'
  start_date: 2015-03-23
date_created: 2018-12-11T11:53:14Z
date_published: 2015-03-01T00:00:00Z
date_updated: 2022-02-03T08:41:46Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: KrPi
doi: 10.1007/978-3-662-46497-7_2
ec_funded: 1
file:
- access_level: open_access
  checksum: 3c5093bda5783c89beaacabf1aa0e60e
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:15:17Z
  date_updated: 2020-07-14T12:45:08Z
  file_id: '5136'
  file_name: IST-2016-679-v1+1_180.pdf
  file_size: 450665
  relation: main_file
file_date_updated: 2020-07-14T12:45:08Z
has_accepted_license: '1'
intvolume: '      9015'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2015/180
month: '03'
oa: 1
oa_version: Submitted Version
page: 31 - 60
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '259668'
  name: Provable Security for Physical Cryptography
publication: 12th Theory of Cryptography Conference
publication_identifier:
  isbn:
  - 978-3-662-46496-0
publication_status: published
publisher: Springer Nature
publist_id: '5505'
pubrep_id: '679'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Key-homomorphic constrained pseudorandom functions
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 9015
year: '2015'
...