Zero-knowledge Proofs

Lecture Overview

A zero-knowledge proof protocol is a kind of interactive proof system where the prover's secret knowledge is still kept secret from the verifier. In this lecture, we will see a few zero-knowledge protocols.

Zero-Knowledge Proof Protocol

Prover, verifier, and interaction

A zero-knowledge proof protocol is a variant of interactive proof system. In an interactive proof system, typically there are two parties involved: prover and verifier.

A statement X is publicly given. That is, both the prover and the verifier know X.
Prover wants to prove that a given statement X is true.
Verifier would like to verify that statement X is indeed true.

The way the verifier checks the validity of statement X is through the interaction between the prover and the verifier.

Statement X?

Any statement is a good candidate for our context as long as it is true or false definitely. Examples of statement of X include:

65537 is a prime number.
According to this map (assume some map is given), the closest airport from the USNA is BWI.
123456789012345 is an encryption of "Hello World" with RSA public key N = 246309498280854877024880505554014023829 and e = 17. (This is a false statement)

Completeness and Soundness

A good interactive proof system should satisfy completeness and soundness.

Completeness. If statement X is true, then after the protocol execution, the verifier will be convinced that X is true.
Soundness. If statement X is false, there should be no way of running the protocol after which the verifier believes that X is true.

Zero-knowledge

Sometimes the prover has an additional secret piece of information about statement X. For example, when X is an encryption, the secret information can be the decryption key. In this case, we can think of two desirable properties that we would like to achieve:

The prover doesn't want to reveal this secret to the verifier (according to the zero-knowledge property).
The prover still wants to prove the validity of statement X (i.e., completeness and soundness).

Zero-knowledge proofs (ZKP) satisfy both of these seemingly conflicting requirements at the same time!

ZKP for The Ali Baba cave (from Wiki)

In paper How to Explain Zero-Knowledge Protocols to Your Children, the authors convey the basic concepts of a zero-knowledge protocol.

Setting

As shown on the right, we have a cave that is shaped like a ring.

There is an entrance on the left side.
Inside the case, there is a magic door that blocks people from proceeding.

Given this cave, consider the following scenario:

Peggy (prover) has uncovered the secret word used to open a magic door in a cave.
Victor (verifier) wants to know whether Peggy knows the secret word.
However, Peggy does not want to reveal her knowledge (i.e., the secret word) to Victor.

Protocol

Step 1: Peggy randomly takes either path A or B, while Victor waits outside. Victor is not allowed to see which path she takes.

Step 2: Now, Victor enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen at random.

Step 3: If Peggy exits from the path that Victor has chosen, Victor declares "accept". Otherwise, Victor declares "reject.

Completeness and Soundness

Completeness. If the statement is true (i.e., if Peggy knows the secret word), then Victor will always declare "accept".
Soundness. If the statement is false (i.e., if Peggy doesn't know the secret word), the probability that Victor declares "reject" is 1/2.
Achieving stronger soundness. Consider the following change:
Run this game 30 times. Victor declares "accept" only if Peggy exits from the right path all the time. Otherwise, he declares "reject".
If the statement is false, the probability that Victor declares "accept" is $\frac 1 {2^{30}}$ (roughly 1 in a billion).

Zero-knowledge

Now, let's think about the zero-knowledge (ZK) property. That is, we need to check whether the play of this game reveals any information about the secret word.

Warning: The ZK property is meaningful only if the statement is true. If a statement is false, there is no secret to talk about!

Observe that even if Victor is wearing a hidden camera that records the whole game, the only thing the camera will record is as follows:

In one case Victor shouting "A!" and Peggy appearing at A.
In the other case Victor shouting "B!" and Peggy appearing at B.

A recording of this type would be trivial for any two people to fake without knowing the secret word, requiring only that Peggy and Victor agree beforehand on the sequence of A's and B's that Victor will shout.

More formal definition of the zero-knowledge (ZK) property generalizes this as follows:

Zero Knowledge Property

Suppose that a given statement is true.

A protocol for this statement is a zero-knowledge if the protocol messages are simulatable without knowing the secret.

ZK Proof of Knowledge for Discrete Logarithm

We can apply these ideas to a more realistic application. Peggy wants to prove to Victor that she knows the discrete log of a given value in a given group.

The protocol proceeds as follows:

Completeness and Soundness

Completeness. If Peggy knows $x$, then the check on Victor's side will always be successful.
Soundness. If Peggy doesn't know $x$, she cannot guess the correct value $s$. This is because $s$ is really a single random number (due to the random challenge $c$ from Victor) that Peggy needs to find out of $q$ many different possibilities. Here, $q$ is an exponentially large number such as $2^{1024}$.
If we want to be more formal, we need to show that if one can take Peggy's proving machine, the actual discrete logarithm $x$ can be extracted. But, this is out of the scope of this course.

Zero-knowledge

Now, let's think about the zero-knowledge (ZK) property. Recall that this need us to create a simulating strategy of the protocol messages without knowing the secret $x$. \[ \mbox{Sample the protocol messages } (R, c, s) \mbox{ with the following properties: } \]

$R$ is random in mod $p$.
$c$ is random in mod $q$.
$s$ is a number such that $g^s = R \cdot y^c \pmod{p}$

Sampling these messages turns out to be quite easy:

Choose a random $c$.
Choose a random $s$.
Compute $R = g^s \cdot (y^c)^{-1} \pmod{p}$.
Output $(R, c, s)$.

Note in the real protocol, Peggy knows $r$ such that $R = g^r \bmod p$. However, the simulation algorithm doesn't know this. However, this different doesn't matter, as long as $R$ is random, which is the case, the simulation is perfect!

Extensions and Applications

ZKP for any NP problem

Note: The class NP contains all the problems that are verifiable in polynomial time.

It is known that there is a zero-knowledge proof protocol for an NP-complete problem. This means that we also have a zero-knowledge proof protocol for any NP problem.

If you haven't taken the Algorithms course:

The main takeaway is that there is a zero-knowlege proof protocol for any natural problems.

Applications

Authentication systems. Zero-knowledge proofs can be useful in authentication systems where one party wants to prove its identity to a second party via some secret information (such as a password) but doesn't want the second party to learn anything about this secret. In August 2021, Cloudflare, an American web infrastructure and security company decided to use a zero-knowledge proofs mechanism for private web verification using vendor hardware. See here.
Nuclear disarmament. In 2016, the Princeton Plasma Physics Laboratory and Princeton University demonstrated a technique that may have applicability to future nuclear disarmament talks. It would allow inspectors to confirm whether or not an object is indeed a nuclear weapon without recording, sharing or revealing the internal workings which might be secret. See here and here.
Blockchains. Zero-knowledge proofs were applied in Zerocoin and Zerocash protocols which resulted in the birth of Zcoin (later rebranded as Firo in 2020) and Zcash cryptocurrencies in 2016. Here, zero-knowledge proofs are used to hide transactions and thereby achieving anonymity. See here and here.