Paper 2020/090

Witness Maps and Applications

Suvradip Chakraborty, Manoj Prabhakaran, and Daniel Wichs


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 $\mathbf{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. \medskip Our main construction is a DMWM for all $\mathbf{NP}$ relations, assuming sub-exponentially secure indistinguishability obfuscation ($i\mathcal{O}$), 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 $i\mathcal{O}$ 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 $i\mathcal{O}$ and sub-exponentially secure OWF. \medskip 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)$.

Available format(s)
Publication info
A major revision of an IACR publication in PKC 2020
Witness MapsZero KnowledgeLossy Trapdoor FunctionsLeakageTamperingSignatures.
Contact author(s)
danwichs @ gmail com
manojmp @ gmail com
2020-02-05: revised
2020-02-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Suvradip Chakraborty and Manoj Prabhakaran and Daniel Wichs},
      title = {Witness Maps and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2020/090},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.