Witness maps and applications

Chakraborty S, Prabhakaran M, Wichs D. 2020.Witness maps and applications. In: Public-Key Cryptography. vol. 12110, 220–246.

Book Chapter | Published | English

Scopus indexed
Chakraborty, SuvradipISTA; Prabhakaran, Manoj; Wichs, Daniel
Book Editor
Kiayias, A
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. Our 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. As 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) .
Publishing Year
Date Published
Book Title
Public-Key Cryptography
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.

Cite this

Chakraborty S, Prabhakaran M, Wichs D. Witness maps and applications. In: Kiayias A, ed. Public-Key Cryptography. Vol 12110. LNCS. Cham: Springer Nature; 2020:220-246. doi:10.1007/978-3-030-45374-9_8
Chakraborty, S., Prabhakaran, M., & Wichs, D. (2020). Witness maps and applications. In A. Kiayias (Ed.), Public-Key Cryptography (Vol. 12110, pp. 220–246). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-45374-9_8
Chakraborty, Suvradip, Manoj Prabhakaran, and Daniel Wichs. “Witness Maps and Applications.” In Public-Key Cryptography, edited by A Kiayias, 12110:220–46. LNCS. Cham: Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45374-9_8.
S. Chakraborty, M. Prabhakaran, and D. Wichs, “Witness maps and applications,” in Public-Key Cryptography, vol. 12110, A. Kiayias, Ed. Cham: Springer Nature, 2020, pp. 220–246.
Chakraborty S, Prabhakaran M, Wichs D. 2020.Witness maps and applications. In: Public-Key Cryptography. vol. 12110, 220–246.
Chakraborty, Suvradip, et al. “Witness Maps and Applications.” Public-Key Cryptography, edited by A Kiayias, vol. 12110, Springer Nature, 2020, pp. 220–46, doi:10.1007/978-3-030-45374-9_8.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access


Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search