Zero-Knowledge Proofs

Zero-Knowledge proofs are a beautiful piece of cryptography. The classical ones are interactive and probabilistic proof systems that rely on a lot of communication between the prover and the verifier, though as we'll see at the end, that interaction can be compiled away (Goldwasser et al. [3]).

Interactive Proving Models

Let's first walk through interactive proof-based systems. Let us assume a Prover $P$ that proves a certain statement in exponential time. We need to ensure that it gets verified by the Verifier $V$. However, if there are $n$ Verifier machines that are involved in the verification of this proof, it's going to take $n$*exponential time to ensure the validation. This is a long time. Let us now restrict $V$ to be a polynomial time machine, i.e. it can only run algorithms in polynomial time. However, the Prover $P$ still takes exponential time. We need to ensure that $P$ convinces $V$ of the correctness of its proof without exceeding any time-bounds.

The way to do this is to allow for a dialogue between $P$ and $V$. If $V$ can exchange information with $P$, we might be able to use this information for validating the proof. This type of proof system is called an Interactive Proof System. This is better explained with an example (Rosen [2]). Let us assume the graph non-isomorphism problem.

Graphs $G_1$ and $G_2$ are isomorphic if all nodes of $G_1$ can be reordered to form a graph identical to $G_2$. It's a problem that does not have a known polynomial time algorithm. If we want to know if two graphs A and B are not isomorphic, we can use the prover $P$ to create a proof for it. Since, $P$ has no time bound, it can generate the proof for this. However, if $P$ were to send the proof to the $V$ machines, they might not be able to verify it since they are restricted to polynomial times. Here is where we can use the power of interactions between $P$ and $V$. $P$ does not need to send any information about how it proved the non-isomorphism to $V$, it just needs to send which of $G_1$ and $G_2$ was used, i.e. a single bit. $V$ can then based on that information verify if the proof is correct. It can do that in the following manner:

1. $V$ picks either $G_1$ or $G_2$ at random and reorders its vertices randomly to construct graph $H$. It then sends that to $P$
2. $P$ uses arbitrary computing power and finds whether $G_1$ or $G_2$ is isomorphic to H. Then, it communicates that to $V$.
3. $V$ checks whether that's the correct original graph to affirm if $P's$ proof is correct.

The above algorithm seems to be correct, but the probability of a dishonest $P$ identifying the correct graph is $0.5$. That means 50% of the time, $P$ might have an incorrect proof but will end up sending the right original graph to $V$. To reduce this error probability, $V$ repeats the process $n$ times, so the probability reduces from $0.5$ to $(0.5)^n$. For a large $n$, this probability gets extremely small. Also, this kind of interactive proof systems are analogous to the client-server model of the web in the aspects of cryptography.

Notice that the above interactive model already protects one of the two parties, and it isn't $P$. $V$ never has to trust $P$: a lying prover gets caught with probability at least $1 - (0.5)^n$ no matter how much computing power it throws at the problem. That property is called soundness, and it exists entirely for $V$'s benefit. Paired with completeness, where an honest $P$ always convinces an honest $V$, it is what makes the thing a proof system at all.

What the model hands $P$ is nothing. Every message $P$ sends becomes $V$'s to keep, study and pass along, and no part of the protocol bounds what $V$ walks away with. Short messages are not the same thing as harmless ones. So the natural question is whether we can supply the missing half.

This is where zero-knowledge proofs shine - they are the same kind of guarantee pointed the other way, shielding $P$ from $V$ rather than $V$ from $P$. A powerful machine $P$ does not need to send all information to the resource-limited $V$, it can convince $V$ of the proof's correctness without communicating any information about the proof. Completeness, soundness and zero-knowledge are the three properties every protocol below has to satisfy.

Deep Dive

I claim to you that $P$ does not need to send the proof's correctness to $V$. $P$ and $V$ can communicate in a manner such that $P$ does not need to send the proof, or whether the answer is correct. It just needs to convince $V$ of its correctness. The problem might seem similar, rather it becomes a whole new idea. $V$ can communicate a random key $K$ to $P$, $P$ can use $K$ along with the proof to generate the value $L$, and send $L$ to $V$. $V$ can use $K$ and $L$ to be sure that the proof is correct. Of course, since randomness is involved, the process is probabilistic.

Here's an analogy of this process, adapted from the classic zero-knowledge cave explanation (Quisquater et al. [4]): Let's take an example from the movie Mission Impossible: Dead Reckoning I (2023). The "cruciform key" is the tool which we can assume is the secret we wanna keep hidden to prevent an AI from going rogue. Say the key opens a vault with two entrances, A and B, joined on the inside by a locked passage that only the complete key can open. $P$ claims to hold that key. Our verifier $V$ (Ethan Hunt) wants to be sure of it, but $P$ won't hand the key over, and won't even let Ethan watch him use it. How can $P$ prove to Ethan that his key is legit?

Like this. Ethan waits outside while $P$ walks in through whichever entrance he feels like. Once $P$ is inside and out of sight, Ethan calls out the entrance he wants $P$ to come back out of. If $P$ really has the key he can always comply; worst case, he unlocks the internal passage and crosses over. If he doesn't have it, he can only leave the way he came in, so he survives a round only when Ethan happens to name the entrance he already picked, i.e. half the time. Run it $t$ times and a keyless $P$ gets away with it with probability $(0.5)^t$.

Now look at what Ethan is left holding: a list of entrances he chose himself, and footage of a man walking out of them. He could have staged that exact footage without $P$ and without any key, just by telling an accomplice which entrance to use before each round. The recording is worthless as evidence to anyone else, which is precisely why it told Ethan nothing about the key.

A Bit more Math: Quadratic Residue ZK Protocol

This is the concept and now let's dive right into the math with an example. Let us assume the problem of Quadratic Residuity.

$x$ is a quadratic residue of $n = p*q$ if $\exists \space y \in Z_n^{*}$ such that $y^2 = x$ mod $n$. We have $P$ trying to prove that such a $y$ exists and convince $V$ of its existence. However, we don't wanna reveal $y$ to V, and instead rely on a ZK protocol. We assume only $P$ knows the $p$ and $q$, the factors of $n$. Hence, it can figure out the $y$ for which $x$ is the quadratic residue.

The protocol works as follows: $P$ randomly selects a value $k \in_R Z_n^{*}$ and computes the value $a = k^2$ mod $n$. It then sends $a$ to $V$. $V$ then randomly selects a bit $b \in \\{0,1\\}$ and sends $b$ to $P$.

• If $b = 0$, P sends the value $k$ to $V$. $V$ then verifies whether $a = k^2$ mod $n$
• If $b = 1$, P computes $s = k * y$ and sends $s$ to V. V then verifies if $s^2 = a*x$ mod $n$. This is true because $s^2 = k^2 * y^2 = a * x$ mod $n$.

This protocol ensures that $V$ only knows that $P$ is correct, but does not receive any information about the proof, only randomness. Hence, it is a zero-knowledge protocol. A "fake" or "dishonest" prover might be wrong $50 \\%$ of the time, but when the protocol is used repeatedly, maybe $t$ times, reduces the probability of error down to $0.5^t$. This protocol is zero-knowledge because $V$ can simulate (or "fake") the entire interaction without any access to the secret or any help from the $P$.

Wrap Up

A zero-knowledge protocol can be used in countless situations, and can ensure that, even in the case of an adversarial attack, no information about the proof (and by extension, the secret) gets communicated. Some use cases:

1. Secure Remote Password (SRP) Protocol: This protocol ensures the client proving that they know the password without the server ever knowing about the password. Even if the network traffic was intercepted, the adversary will receive no information about the password. It's used in Apple's iCloud for storing user passkeys.
2. zk-SNARKS: These are cryptographic protocols used in a blockchain like ZCash. They ensure the validity of the blockchain under the consensus rules, yet the transaction data remains fully hidden. However, zk-SNARKS are slightly different. They are non-interactive, i.e. there's only a single message sent from $P$ to $V$.

References

1. Zero-knowledge proof. Wikipedia.

2. Rosen, A. Introduction to Zero Knowledge.

3. Goldwasser, S., Micali, S., & Rackoff, C. The Knowledge Complexity of Interactive Proof Systems.

4. Quisquater, J.-J., Guillou, L., et al. How to Explain Zero-Knowledge Protocols to Your Children.