Zero-Knowledge proofs are a beautiful piece of cryptography. They are interactive and probabilistic proof systems that rely on a lot of
communication between the prover and the verifier.
Interactive Proving Models
Let’s first walk through interactive proof-based systems. Let us assume a Prover that proves a certain statement in exponential time.
We need to ensure that it gets verified by the Verifier . However, if there are Verifier machines that are involved in the verification
of this proof, it’s going to take *exponential time to ensure the validation. This is a long time. Let us now restrict to be a polynomial time machine, i.e. it can only run algorithms in polynomial time. However, the Prover still takes
exponential time. We need to ensure that convinces of the correctness of its proof without exceeding any time-bounds.
The way to do this is to allow for a dialogue between and . If can exchange information with , 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. Let us assume
the graph isomorphism problem.
Graphs and are isomorphic if all nodes of can be reordered to form a graph identical to . It’s a problem that does not have a
polynomial time algorithm. If we want to know if two graphs A and B are isomorphic, we can use the prover to create a proof for it. Since,
has no time bound, it can generate the proof for this. However, if were to send the proof to the 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 and . does not need
to send any information about how it proved the isomorphism to , it just needs to send if and are isomorphic or not, i.e. a single
bit. can then based on that information verify if the proof is correct. It can do that in the following manner:
picks either or at random and
reorders its vertices randomly to construct graph . It then sends that to
uses arbitrary computing power and finds whether or is isomorphic to H. Then, it communicates that to .
checks whether that’s the correct original graph to affirm if proof is correct.
The above algorithm seems to be correct, but the probability of identifying the correct graph is .
That means 50% of the time, might have an
incorrect proof but will end up sending the right original graph to . To reduce this error probability, repeats the process times, so the probability
reduces from to . For a large , 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.
The above interactive model relies on communication to build proving systems. However, it uses another aspect that is significant to security of
systems, i.e. trust. and rely on a sense of trust since is sending the proof’s correctness (whether the graphs
are isomorphic) to . What if we made the process a bit more trustless?
This is where zero-knowledge proofs shine - they build a layer of trustlessness within the interactive model between and
. A powerful machine does not need to send all information to the resource-limited , it can convince
of the proof’s correctness without communicating any information about the proof.
Deep Dive
I claim to you that does not need to send the proof’s correctness to . and can communicate in a manner such that does not need to
send the proof, or whether the answer is correct. It just needs to convince of its correctness. The problem might seem similar, rather it
becomes a whole new idea. can communicate a random key to , can use along with the proof to generate the value , and send to .
can use and 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:
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. Let the key’s model be stored by , the most secure vault in the world. can
create multiple replicas of the key and cannot be broken, ever. Now, our verifier (Ethan Hunt) wants to ensure that actually has the
correct 3D key configuration. He, being the world’s best agent, has a half-key, which was the only part of the key released into the
wild by Russian agents. He also has a machine that can take a hash of the other half-key and verify that the key works. Hashing is one-way
so no one can reproduce the key from any half. How can prove to Ethan that his key is legit?
Using the concept of Zero-Knowledge proofs, can take Ethan’s half, use his 3D key model to create the other half, and confirm if Ethan’s
key is correct. If that is true, he can send off the half key’s hash to Ethan using its arbitrary computing power. Ethan uses it to
confirm if the hash is correct and he is sure his key is correct.
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.
is a quadratic residue of if such that
mod . We have trying to prove that such a exists and convince of its existence.
However, we don’t wanna reveal to V, and instead rely on a ZK protocol. We assume only knows the and
, the factors of . Hence, it can figure out the for which is the quadratic residue.
The protocol works as follows: randomly selects a value and computes the value
mod . It then sends to . then randomly selects a bit
and sends to .
If , P sends the value to . then verifies whether mod
If , P computes and sends to V. V then verifies if
mod . This is true because mod .
This protocol ensures that only knows that 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
of the time, but when the protocol is used repeatedly, maybe times, reduces the probability of error
down to . This protocol is zero-knowledge because can simulate (or “fake”) the entire
interaction without any access to the secret or any help from the .
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:
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.
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 encrypted.
However, zk-SNARKS are slightly different. They are non-interactive, i.e.
there’s only a single message sent from to .
