This is the second one of my article series on Zero Knowledge. First one was a very abstract example to point out what we are looking for. Now we are continuing with the first emergence of ZK protocols in the literature. You may need your pencil 📝 in this one…

We will examine the interactive proof scheme which showed effectively that proving a knowledge without revealing anything about the secret is possible. There are lot to cover so bear with me. Hopefully, we will get closer what a real ZK protocol may offer.

TLDR: If an interaction cannot be simulated, we lose ZKness since the prover now loses her chance to deny the possession of the secret.

Let us remember that ZK is a property. It can be thought as all or none, if even one thing is revealed, ZK is lost. As we examined earlier, the case in which Peggy cannot deny that she knows the secret means we do not have ZK property. As we understood that, we should ofcourse make things harder and more complicated now. It will get easier the more we see internal mechanics and components of these schemes.

Interactive Proof Systems

Interaction of parties is essentially communicating back and forth but only the specified information. That is to keeping some information secret. As we will see, randomness is neeeded for such systems to work, so we have to secure this random number generation and sometimes the random number itself. We call such systems interactive proof systems.

So the question raised was and still is, how much knowledge is obtained by the verifier in an interactive proof system. We define interactive zero-knowledge proof system for a problem$^{[1]}$ as follows : if the Prover tells nothing but her solution is valid for the specified problem. We knew this already from the Cave example, but we will add something here now : the above statement should hold even if the Verifier is trying to obtain some information by tricking the Prover. It was not that trivial in the Cave example since we discarded most of unwanted details to deliver basics. So, even if the Verifier is not abiding the protocol and acts deceptively, he should not be able to obtain anything.

Let us examine an example problem $^{[A]}$ which has an interactive proof. We will show an interactive proof system for membership in Quadratic Residue(QN) $^{[3]}$ . Let us say our inputs are $x$ and $y$. The question is if y is a Quadratic Non-Residue mod x or not. Let $n$ be the length of the binary representation $^{[2]}$ of $x$. Verifier starts by generating a random number $r$ of which the binary representation $b_0, b_1, ... , b_n$ length also is $n$. The Verifier generates $r$ by tossing a coin for each bit and say making that bit 1 for heads, 0 for tails. Coin toss is a symbolic approach to indicate that this process should be a random process, i.e. there should not be any deterministic precursors to the selection of $r$ since if so and the Prover discovers such a pattern, she could deceive the Verifier . We will examine this scenario in a minute. After the Verifier generates $r$, he then begins to form a string $\alpha$ as following : the Verifier computes values $z_1, z_2, ... z_n$ such that each $z_i$ is a random value, $0<z<x$, and $gcd(z_i, x)=1$ . The Verifier then computes $w_1, w_2, ... w_n$ such that for every $b_i$ in bits of $r$, if $b_i = 0$ then $w_i = z_i^2 mod x$; if $b_i = 1$ then $w_i = (z_i^2y) mod x$. In simpler terms, if $b_i = 0$, the $w_i$ corresponding to this turn will be a quadratic residue in $mod x$; if $b_i = 1$, the $w_i$ corresponding to that turn will NOT be a quadratic residue in $mod x$. So the Prover somehow computes whether or not $w_i$ is a QR $mod x$ or not, and sends to the Verifier a sequence of bits $c_1, c_2, ..., c_i$ such that $c_i=0$ if and only if $w_i$ is a QR $mod x$, $c_i-1$ otherwise. B checks if $b_i=c_i$ for every $i$, and if so is “convinced” that $y$ is in QNR $mod x$. The reasoning is as follows: if for every $b_i$, $b_i=c_i$, it means the Prover who can somehow compute if a number is in QR $mod x$ or not, could not compute a number $\gamma$ such that $y=\gamma^2 mod x$. If she could, $w_i = (z_i^2y) mod x$ would result in $w_i = (z_i^2\gamma^2) mod x$ this be a QR $mod x$ and would result a bit 0 contrary to $b_i$ which is equal to 1 instead since the Verifier assumed that $y$ is in QNR $mod x$.

Let us peak another problematic situation between Victor and Peggy. Those two appearantly have trust problems…

Figure 1 : Interactive proof schema, the arrows are not horizontal to represent time which is assumed to flow from above to below in this case

Figure 2 :A colored graph sample

http://web.mit.edu/~ezyang/Public/graph/svg.html

The Knowledge Complexity of Interactive Proof Systems - Shafi Goldwasser, Silvio Micali, and Charles Rackoff

Figure 3 : Victor chose edge $e_i$ and Peggy revealed the vertices connected by the $e_i$. Seeing that vertices belong to the solution color set and different Victor will note this run as in the cave example and re-run the protocol

$^{[1]}$ problem -> a string belonging to a language.
$^{[2]}$ binary representation. i.e. the number of 1s and 0s in the representation.
$^{[3]}$
$^{[4]}$
$^{[5]}$