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, noninteractive, 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 tamperresilient 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 (dvUWM)'' setting is \emph{equivalent} to witness PRFs. Moreover, we consider two flavors of such dvUWMs, 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{pseudoUWMs} where the witness map is allowed to be \emph{pseudodeterministic}  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 $11/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 apriori fixed polynomial $p$, independent of the length of the statement $x$ or witness $w$. Such CWMs are implied by succinct noninteractive arguments (SNARGs). We show that such CWMs imply NIZKs, and therefore lie somewhere between NIZKs and SNARGs. \end{itemize}
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 A minor revision of an IACR publication in PKC 2023
 Contact author(s)

suvradip1111 @ gmail com
mp @ cse iitb ac in
wichs @ ccs neu edu  History
 20230308: approved
 20230308: received
 See all versions
 Short URL
 https://ia.cr/2023/343
 License

CC0
BibTeX
@misc{cryptoeprint:2023/343, author = {Suvradip Chakraborty and Manoj Prabhakaran and Daniel Wichs}, title = {A Map of Witness Maps: New Definitions and Connections}, howpublished = {Cryptology ePrint Archive, Paper 2023/343}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/343}}, url = {https://eprint.iacr.org/2023/343} }