---
_id: '10865'
abstract:
- lang: eng
  text: "We introduce the notion of Witness Maps as a cryptographic notion of a proof
    system. A Unique Witness Map (UWM) deterministically maps all witnesses for an
    \  NP  statement to a single representative witness, resulting in a computationally
    sound, deterministic-prover, non-interactive witness independent proof system.
    A relaxation of UWM, called Compact Witness Map (CWM), maps all the witnesses
    to a small number of witnesses, resulting in a “lossy” deterministic-prover, non-interactive
    proof-system. We also define a Dual Mode Witness Map (DMWM) which adds an “extractable”
    mode to a CWM.\r\nOur main construction is a DMWM for all   NP  relations, assuming
    sub-exponentially secure indistinguishability obfuscation (  iO ), along with
    standard cryptographic assumptions. The DMWM construction relies on a CWM and
    a new primitive called Cumulative All-Lossy-But-One Trapdoor Functions (C-ALBO-TDF),
    both of which are in turn instantiated based on   iO  and other primitives. Our
    instantiation of a CWM is in fact a UWM; in turn, we show that a UWM implies Witness
    Encryption. Along the way to constructing UWM and C-ALBO-TDF, we also construct,
    from standard assumptions, Puncturable Digital Signatures and a new primitive
    called Cumulative Lossy Trapdoor Functions (C-LTDF). The former improves up on
    a construction of Bellare et al. (Eurocrypt 2016), who relied on sub-exponentially
    secure   iO  and sub-exponentially secure OWF.\r\nAs an application of our constructions,
    we show how to use a DMWM to construct the first leakage and tamper-resilient
    signatures with a deterministic signer, thereby solving a decade old open problem
    posed by Katz and Vaikunthanathan (Asiacrypt 2009), by Boyle, Segev and Wichs
    (Eurocrypt 2011), as well as by Faonio and Venturi (Asiacrypt 2016). Our construction
    achieves the optimal leakage rate of   1−o(1) ."
acknowledgement: We would like to thank the anonymous reviewers of PKC 2019 for their
  useful comments and suggestions. We thank Omer Paneth for pointing out to us the
  connection between Unique Witness Maps (UWM) and Witness encryption (WE). The first
  author would like to acknowledge Pandu Rangan for his involvement during the initial
  discussion phase of the project.
article_processing_charge: No
author:
- first_name: Suvradip
  full_name: Chakraborty, Suvradip
  id: B9CD0494-D033-11E9-B219-A439E6697425
  last_name: Chakraborty
- first_name: Manoj
  full_name: Prabhakaran, Manoj
  last_name: Prabhakaran
- first_name: Daniel
  full_name: Wichs, Daniel
  last_name: Wichs
citation:
  ama: 'Chakraborty S, Prabhakaran M, Wichs D. Witness maps and applications. In:
    Kiayias A, ed. <i>Public-Key Cryptography</i>. Vol 12110. LNCS. Cham: Springer
    Nature; 2020:220-246. doi:<a href="https://doi.org/10.1007/978-3-030-45374-9_8">10.1007/978-3-030-45374-9_8</a>'
  apa: 'Chakraborty, S., Prabhakaran, M., &#38; Wichs, D. (2020). Witness maps and
    applications. In A. Kiayias (Ed.), <i>Public-Key Cryptography</i> (Vol. 12110,
    pp. 220–246). Cham: Springer Nature. <a href="https://doi.org/10.1007/978-3-030-45374-9_8">https://doi.org/10.1007/978-3-030-45374-9_8</a>'
  chicago: 'Chakraborty, Suvradip, Manoj Prabhakaran, and Daniel Wichs. “Witness Maps
    and Applications.” In <i>Public-Key Cryptography</i>, edited by A Kiayias, 12110:220–46.
    LNCS. Cham: Springer Nature, 2020. <a href="https://doi.org/10.1007/978-3-030-45374-9_8">https://doi.org/10.1007/978-3-030-45374-9_8</a>.'
  ieee: 'S. Chakraborty, M. Prabhakaran, and D. Wichs, “Witness maps and applications,”
    in <i>Public-Key Cryptography</i>, vol. 12110, A. Kiayias, Ed. Cham: Springer
    Nature, 2020, pp. 220–246.'
  ista: 'Chakraborty S, Prabhakaran M, Wichs D. 2020.Witness maps and applications.
    In: Public-Key Cryptography. vol. 12110, 220–246.'
  mla: Chakraborty, Suvradip, et al. “Witness Maps and Applications.” <i>Public-Key
    Cryptography</i>, edited by A Kiayias, vol. 12110, Springer Nature, 2020, pp.
    220–46, doi:<a href="https://doi.org/10.1007/978-3-030-45374-9_8">10.1007/978-3-030-45374-9_8</a>.
  short: S. Chakraborty, M. Prabhakaran, D. Wichs, in:, A. Kiayias (Ed.), Public-Key
    Cryptography, Springer Nature, Cham, 2020, pp. 220–246.
date_created: 2022-03-18T11:35:51Z
date_published: 2020-04-29T00:00:00Z
date_updated: 2023-09-05T15:10:02Z
day: '29'
doi: 10.1007/978-3-030-45374-9_8
editor:
- first_name: A
  full_name: Kiayias, A
  last_name: Kiayias
intvolume: '     12110'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2020/090
month: '04'
oa: 1
oa_version: Preprint
page: 220-246
place: Cham
publication: Public-Key Cryptography
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783030453732'
  - '9783030453749'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Witness maps and applications
type: book_chapter
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 12110
year: '2020'
...