Welcome to the resource topic for 2023/343
Title:
A Map of Witness Maps: New Definitions and Connections
Authors: Suvradip Chakraborty, Manoj Prabhakaran, Daniel Wichs
Abstract:A \emph{witness map} deterministically maps a witness w of some NP statement x into computationally sound proof that x is true, with respect to a public common reference string (CRS). In other words, it is a deterministic, non-interactive, computationally sound proof system in the CRS model. A \emph{unique witness map} (UWM) ensures that for any fixed statement x, the witness map should output the same \emph{unique} proof for x, no matter what witness w it is applied to. More generally a \emph{compact witness map} (CWM) can only output one of at most 2^\alpha proofs for any given statement x, where \alpha is some compactness parameter. Such compact/unique witness maps were proposed recently by Chakraborty, Prabhakaran and Wichs (PKC ‘20) as a tool for building tamper-resilient signatures, who showed how to construct UWMs from indistinguishability obfuscation (iO). In this work, we study CWMs and UWMs as primitives of independent interest and present a number of interesting connections to various notions in cryptography.
\begin{itemize}
\item First, we show that UWMs lie somewhere between witness PRFs (Zhandry; TCC ‘16) and iO – they imply the former and are implied by the latter. In particular, we show that a relaxation of UWMs to the ``designated verifier (dv-UWM)’’ setting is \emph{equivalent} to witness PRFs. Moreover, we consider two flavors of such dv-UWMs, which correspond to two flavors of witness PRFs previously considered in the literature, and show that they are all in fact equivalent to each other in terms of feasibility.
\item Next, we consider CWMs that are extremely compact, with \alpha = O(\log \kappa), where \kappa is the security parameter. We show that such CWMs imply \emph{pseudo-UWMs} where the witness map is allowed to be \emph{pseudo-deterministic} – i.e., for every true statement x, there is a unique proof such that, on any witness w, the witness map outputs this proof with 1-1/p(\lambda) probability, for a polynomial p that we can set arbitrarily large.
\item Lastly, we consider CWMs that are mildly compact, with \alpha = p(\lambda) for some a-priori fixed polynomial p, independent of the length of the statement x or witness w. Such CWMs are implied by succinct non-interactive arguments (SNARGs). We show that such CWMs imply NIZKs, and therefore lie somewhere between NIZKs and SNARGs.
\end{itemize}
ePrint: https://eprint.iacr.org/2023/343
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .