---
_id: '1229'
abstract:
- lang: eng
  text: Witness encryption (WE) was introduced by Garg et al. [GGSW13]. A WE scheme
    is defined for some NP language L and lets a sender encrypt messages relative
    to instances x. A ciphertext for x can be decrypted using w witnessing x ∈ L,
    but hides the message if x ∈ L. Garg et al. construct WE from multilinear maps
    and give another construction [GGH+13b] using indistinguishability obfuscation
    (iO) for circuits. Due to the reliance on such heavy tools, WE can cur- rently
    hardly be implemented on powerful hardware and will unlikely be realizable on
    constrained devices like smart cards any time soon. We construct a WE scheme where
    encryption is done by simply computing a Naor-Yung ciphertext (two CPA encryptions
    and a NIZK proof). To achieve this, our scheme has a setup phase, which outputs
    public parameters containing an obfuscated circuit (only required for decryption),
    two encryption keys and a common reference string (used for encryption). This
    setup need only be run once, and the parame- ters can be used for arbitrary many
    encryptions. Our scheme can also be turned into a functional WE scheme, where
    a message is encrypted w.r.t. a statement and a function f, and decryption with
    a witness w yields f (m, w). Our construction is inspired by the functional encryption
    scheme by Garg et al. and we prove (selective) security assuming iO and statistically
    simulation-sound NIZK. We give a construction of the latter in bilinear groups
    and combining it with ElGamal encryption, our ciphertexts are of size 1.3 kB at
    a 128-bit security level and can be computed on a smart card.
acknowledgement: Research  supported  by  the  European  Research  Council,  ERC  starting  grant
  (259668-PSPC) and ERC consolidator grant (682815 - TOCNeT).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Hamza M
  full_name: Abusalah, Hamza M
  id: 40297222-F248-11E8-B48F-1D18A9856A87
  last_name: Abusalah
- first_name: Georg
  full_name: Fuchsbauer, Georg
  id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
  last_name: Fuchsbauer
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
citation:
  ama: 'Abusalah HM, Fuchsbauer G, Pietrzak KZ. Offline witness encryption. In: Vol
    9696. Springer; 2016:285-303. doi:<a href="https://doi.org/10.1007/978-3-319-39555-5_16">10.1007/978-3-319-39555-5_16</a>'
  apa: 'Abusalah, H. M., Fuchsbauer, G., &#38; Pietrzak, K. Z. (2016). Offline witness
    encryption (Vol. 9696, pp. 285–303). Presented at the ACNS: Applied Cryptography
    and Network Security, Guildford, UK: Springer. <a href="https://doi.org/10.1007/978-3-319-39555-5_16">https://doi.org/10.1007/978-3-319-39555-5_16</a>'
  chicago: Abusalah, Hamza M, Georg Fuchsbauer, and Krzysztof Z Pietrzak. “Offline
    Witness Encryption,” 9696:285–303. Springer, 2016. <a href="https://doi.org/10.1007/978-3-319-39555-5_16">https://doi.org/10.1007/978-3-319-39555-5_16</a>.
  ieee: 'H. M. Abusalah, G. Fuchsbauer, and K. Z. Pietrzak, “Offline witness encryption,”
    presented at the ACNS: Applied Cryptography and Network Security, Guildford, UK,
    2016, vol. 9696, pp. 285–303.'
  ista: 'Abusalah HM, Fuchsbauer G, Pietrzak KZ. 2016. Offline witness encryption.
    ACNS: Applied Cryptography and Network Security, LNCS, vol. 9696, 285–303.'
  mla: Abusalah, Hamza M., et al. <i>Offline Witness Encryption</i>. Vol. 9696, Springer,
    2016, pp. 285–303, doi:<a href="https://doi.org/10.1007/978-3-319-39555-5_16">10.1007/978-3-319-39555-5_16</a>.
  short: H.M. Abusalah, G. Fuchsbauer, K.Z. Pietrzak, in:, Springer, 2016, pp. 285–303.
conference:
  end_date: 2016-06-22
  location: Guildford, UK
  name: 'ACNS: Applied Cryptography and Network Security'
  start_date: 2016-06-19
date_created: 2018-12-11T11:50:50Z
date_published: 2016-06-09T00:00:00Z
date_updated: 2026-04-08T14:10:21Z
day: '09'
ddc:
- '005'
- '600'
department:
- _id: KrPi
doi: 10.1007/978-3-319-39555-5_16
ec_funded: 1
external_id:
  isi:
  - '000386324500016'
file:
- access_level: open_access
  checksum: 34fa9ce681da845a1ba945ba3dc57867
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:17:20Z
  date_updated: 2020-07-14T12:44:39Z
  file_id: '5273'
  file_name: IST-2017-765-v1+1_838.pdf
  file_size: 515000
  relation: main_file
file_date_updated: 2020-07-14T12:44:39Z
has_accepted_license: '1'
intvolume: '      9696'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 285 - 303
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '259668'
  name: Provable Security for Physical Cryptography
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
publication_status: published
publisher: Springer
publist_id: '6105'
pubrep_id: '765'
quality_controlled: '1'
related_material:
  record:
  - id: '83'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Offline witness encryption
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 9696
year: '2016'
...