A Map of Witness Maps: New Definitions and Connections

A 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 unique witness map (UWM) ensures that for any fixed statement x, the witness map should output the same unique proof for x, no matter what witness w it is applied to. More generally a 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.

• 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 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.

• 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 pseudo-UWMs where the witness map is allowed to be 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.

• 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.

1. 1.

   Informally, a \(\lambda \)-BLR-wPRF \(F_K(\cdot )\) guarantees pseudorandomness of the output of the PRF when evaluated on uniformly random inputs, even when the adversary can leak up to \(\lambda \) bits on K. [9] showed how to construct such BLR-wPRF from any OWF.

2. 2.

   Informally, a \(\lambda \)-entropic leakage-resilient PRF \(F_K(\cdot )\) guarantees pseudorandomness of the output of the PRF when evaluated on uniformly random inputs, even when the adversary can get \(\lambda \)-entropic leakage on K. Roughly this means that the PRF key K still has \(k - \lambda \) bits of average min-entropy, even conditioned on the leakage from K. [9] showed how to construct such entropic LR-wPRF from any OWF.

3. 3.

   Note that, the language \(L_R:= \{ x \mid \exists w, (x,w)\in R \}\).

Authors and Affiliations

1. Visa Research, Palo Alto, USA

   Suvradip Chakraborty

2. Department of Computer Science, IIT Bombay, Mumbai, India

   Manoj Prabhakaran

3. Northeastern University, Boston, USA

   Daniel Wichs

4. NTT Research, Palo Alto, USA

   Daniel Wichs

Corresponding author

Correspondence to Suvradip Chakraborty .

Editors and Affiliations

1. Georgia Institute of Technology, Atlanta, GA, USA

   Alexandra Boldyreva

2. Georgia Institute of Technology, Atlanta, GA, USA

   Vladimir Kolesnikov

Reprints and permissions

© 2023 International Association for Cryptologic Research

Policies and ethics