2
$\begingroup$

I am having trouble understanding the difference between Non-Interactive(NIP) and Interactive(IP) Zero Knowledge Proofs as the definitions given to me for the Soundness and Completeness qualities of IP and NIP are seemingly identical. Could someone please contrast IP and NIP? An simple example would also be much appreciated.

$\endgroup$
6
$\begingroup$

A nice example is Schnorr's identification protocol, see here. All notation below is taken from this document, but should not be the important part.

On page 1 they explain the original identification:

  1. $\mathcal{P}$ chooses a random $k\leftarrow[1,r]$ and sends $R=[k]P$ to $\mathcal{V}$.
  2. $\mathcal{V}$ chooses a random "challenge" $e\leftarrow [1,r]$ and sends $e$ to $\mathcal{P}$.
  3. $\mathcal{P}$ computes $s=k+ae\pmod{r}$ and sends $s$ to $\mathcal{V}$.

Note that in step 1 $\mathcal{P}$ sends somethings to $\mathcal{V}$, and in step 2 $\mathcal{V}$ sends something to $\mathcal{P}$. Therefore this zero-knowledge proof is interactive.

Alternatively, you can do the following, given a hash function $H$ (which should satisfy some properties!):

  1. $\mathcal{P}$ chooses a random $k\leftarrow[1,r]$ and computes $R=[k]P$.
  2. $\mathcal{P}$ sets $e=H(R)$.
  3. $\mathcal{P}$ sets $s=k+ae\pmod{r}$.
  4. $\mathcal{P}$ sends $(R,s)$ to $\mathcal{V}$.

Note that only at the very end we need to send the zero-knowledge proof to $\mathcal{V}$, but to construct the proof itself no communication is needed. Therefore this protocol is non-interactive.

$\endgroup$
  • $\begingroup$ I see how you are differentiating between IP and NIP however, the definition of ZK that I have is that I am able to construct a Simulator S such that the distribution of outputs of S is equivalent to the distribution of outputs of the PV conversation. Could you point me to this simulator in your example? Thank you @CurveEnthusiast $\endgroup$ – z.karl Dec 7 '16 at 16:59
  • $\begingroup$ This protocol is very common, so there should be many proofs out there. A quick google search led me to this question, which probably has some answers that are useful: crypto.stackexchange.com/questions/9997/…. To go from interactive to non-interactive protocols, you can look into the "Fiat-Shamir heuristic". $\endgroup$ – CurveEnthusiast Dec 8 '16 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.