Zero-knowledge ($ZK$) protocols are one of the most fundamental cryptographic primitives. Classic results in the 1980s established that one-way functions (OWFs) suffice for constructing $ZK$ for $NP$ (Goldreich-Micali-Wigderson [JACM'91], Naor [CRYPTO’89], Hastad et al. [SICOMP’99]). Moreover, OWFs are, in fact, necessary for $ZK$ for $NP$, due to the classic result ... more >>>
In this paper we study the cryptographic complexity of non-trivial witness-indistinguishable ($WI$) arguments of knowledge. We establish that:
- Assuming that $NP\not\subseteq P/poly,$ the existence of a constant-round computational $WI$ argument of knowledge for $NP$ implies that (infinitely-often) auxiliary-input one-way functions exist.
- Assuming that $NP\not\subseteq P^{Sam}/poly,$ there is no ... more >>>
A central question in the study of interactive proofs is the relationship between private-coin proofs, where the verifier is allowed to hide its randomness from the prover, and public-coin proofs, where the verifier's random coins are sent to the prover.
In this work, we study transformations ...
more >>>