Paper 2020/090
Witness Maps and Applications
Suvradip Chakraborty, Manoj Prabhakaran, and Daniel Wichs
Abstract
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 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 relations, assuming
sub-exponentially secure indistinguishability obfuscation (), 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 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
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 .