Paper 2023/343

A Map of Witness Maps: New Definitions and Connections

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}