Lecture 21: Zero Knowledge Proofs
Review from last lecture
Secure multi-party computation (MPC) solves a seemingly-impossible problem:
Many people, each with their own private data that they do not wish to share, can still perform data analysis collaboratively and only reveal the result!
We can also add integrity and availability using verifiable secret sharing (or VSS). In this case, we can withstand so-called malicious parties that are trying to break both confidentiality and correctness.
Like the Byzantine generals question, VSS has a leader that is re providing information to many other parties. The main differences here are that:
- we are adding confidentiality through secret sharing, and
- there are two stages to the protocol, a dispersal stage and a retrieval stage.
Last time, we constructed a verifiable secret sharing scheme for any number of \(n\) parties, such that:
- at most \(f < n/3\) of them were faulty (since we didn’t use a PKI, we know this is the best possible) and
- \(t < 2n/3\) were colluding to break confidentiality.
This can be used as the basis of MPC constructions with integrity and availability.
More generally:
- It is possible to construct MPC that is secure against an actively malicious adversary Mallory for any threshold of \(t \leq n\) of parties required to reconstruct the data.
- The threshold can potentially be as high as all \(n\) parties if desired, meaning that even if Mallory controls \(n - 1\) parties then data confidentiality and integrity will be guaranteed for the single honest party.
21.1 Motivating question
Can you convince someone that a statement is true, without showing them the evidence or reason why?
Example 1. Two interleaved locks
Example 2. Sudoku puzzle
Example 3. Proof of knowledge of the discrete logarithm of \(h = g^x\). (We saw this in Lecture 4.)
- Prover chooses a random exponent \(k\) and sends \(g^k\) to the verifier.
- Verifier chooses one of two challenges: it requests either
- The discrete log of \(g^k\), or
- The discrete log of \(g^k \cdot h = g^{k+x}\).
- Prover responds to the challenge by sending either \(k\) or \(k+x\), as appropriate.
The verifier accepts this proof only if \(g\) raised to the power of the final message equals the challenge.
21.2 The idea of ZK proofs
A zero knowledge proof is a protocol involving two parties: a prover and a verifier.
(Rather than calling the parties Alice and Bob, typically the parties are called Peggy and Victor.)
| Prover Peggy\((x, w)\) | Verifier Victor\((x)\) | |
|---|---|---|
|
\(\begin{array}{c} \underset{\longleftarrow}{\pi} \\ \longrightarrow \\ \vdots \\ \longrightarrow \end{array}\) |
|
| output: Accept or Reject |
Before the protocol starts:
- There is a claimed statement \(x\) (i.e., the Sudoku puzzle) that is common knowledge: both the prover Peggy and verifier Victor know it.
- The prover Peggy also has a witness \(w\) (i.e., the solution to the Sukodu puzzle).
- It is also common knowledge that there is an efficiently-computable check program \(C(x, w)\) that can determine that the statement is true, given \(x\) and \(w\). (So: Peggy can run \(C\), but Victor cannot since he doesn’t have \(w\).)
Once the protocol ends: the verifier outputs its judgment about whether to Accept or Reject the claim that \(x\) is true.
Note that the prover has no output. It already knows everything, and isn’t trying to learn new information through the interaction. Instead it is just trying to convince the verifier that \(x\) is true.
What makes this problem interesting is: neither party fully trusts the other one.
If Victor fully trusted Peggy, he could just take her word that the claimed statement is true. Instead, he wants to be convinced that the statement \(x\) is true. That is: he is concerned about the integrity of the proof.
If Peggy fully trusted Victor, then she could just send him the solution \(w\) and let him verify it for himself. Instead, Peggy wants to keep \(w\) to herself. That is, she is concerned about the confidentiality of the proof.
The parties can have as many or as few rounds of interaction as the verifier wants. You can think of the interactive dialogue as Victor issuing challenges and Peggy sending responses to these challenges.
By the end of the interactive conversation, the verifier should be convinced that:
- The statement is true.
- Optionally, Peggy knows why the statement is true. This is called a proof of knowledge.
To understand the difference between a proof and a proof of knowledge: consider the following two statements given a group element \(h = g^s\), where \(g\) and \(h\) are publicly known.
- There exists a discrete log \(s = \log_{g}(h)\).
- I know the discrete log \(s = \log_{g}(h)\).
21.3 Defining ZK proofs
| Prover Peggy\((x, w)\) | Verifier Victor\((x)\) | |
|---|---|---|
|
|
\(\begin{array}{c} \underset{\longleftarrow}{\pi} \\ \longrightarrow \\ \vdots \\ \longrightarrow \end{array}\) |
|
| output: Accept or Reject |
Formally, a zero knowledge proof is an interactive protocol \(\pi\) that satisfies three properties.
- Completeness: every valid proof should be accepted by the verifier.
In more detail: if the statement \(x\) is true and both Peggy and Victor act honestly, then at the end of the protocol Victor will output True.
- Soundness: nearly all invalid proofs should be rejected by the verifier.
In more detail: if the statement \(x\) is false and Victor is honest, then it is infeasible for any prover Peggy (even a malicious/faulty one) to deceive Victor. That is, Victor will output False, except maybe with some probability \(\varepsilon\) of making an error and reaching a decision of True instead.
An extension of this property, called knowledge soundness, states that:
if Peggy can convince Victor to accept the proof, then she must have a witness \(w\) that explains why the statement is true.
I’m not going to provide a rigorous definition of this property in this class.
- Zero knowledgeness: if the statement \(x\) is true and Peggy is honest, then it is infeasible for any verifier Victor (even a malicious/faulty one) to learn anything from the proof beyond the fact that the statement is true.
One of the formative achievements in modern cryptography is to devise a way to formalize this claim – that is, to prove a negative.
Here’s how it works. The main insight is to create a new computer program called the simulator \(S\).
- The simulator is a figment of Victor’s imagination – it does not really exist.
- The simulator’s job is to take on the role of the prover and to forge a proof.
Wait hang on, that doesn’t sound right! If a proof can be forged, then it wouldn’t be sound!
To resolve this conundrum, we only insist that the simulator forge a proof back to Victor himself.
That is: the simulator will take on the role of the prover, and it will interact with Victor. Every time that Victor issues a challenge, the simulator will respond to it too, just like the real prover does.
So we can imagine two scenarios:
- Victor is talking to a real prover Peggy (who has a witness).
| Prover Peggy\((x, w)\) | Verifier Victor\((x)\) | |
|---|---|---|
|
|
\(\begin{array}{c} \underset{\longleftarrow}{\pi} \\ \longrightarrow \\ \vdots \\ \longrightarrow \end{array}\) |
|
| output: Accept or Reject |
- Victor is talking to this imaginary simulator (who doesn’t know the witness).
| Simulator\((x)\) | Verifier Victor\((x)\) | |
|---|---|---|
|
\(\begin{array}{c} \underset{\longleftarrow}{\pi_\text{Fake}} \\ \longrightarrow \\ \vdots \\ \longrightarrow \end{array}\) |
|
| output: Accept or Reject |
A proof satisfies the zero knowledge property if:
For any verifier \(V\) and statement \(x\), there exists a simulator \(S\) such that it is infeasible to tell the difference between the random variables \(\pi_\text{Real}\) and \(\pi_\text{Fake}\).
It is easiest to think through the concept of simulation using an example. Let’s go back to our Sudoku puzzle from yesterday’s lab.
Every time the verifier Victor issues a challenge to open one row, colum, or grid, it already “knows” what it is expecting to see:
the numbers 1 through 9, in a random order, except for the numbers that were already part of the puzzle.
Hence: it isn’t really the cards themselves that convince Victor that the proof is true.
Instead what convinces Victor is that:
- Peggy already committed to the cards beforehand (i.e., placed them facedown and cannot change them later), before Victor’s challenge
- The publicly visible cards correspond to the actual puzzle \(x\) that Victor wanted to know whether it is solveable.
- Peggy is capable of responding to many challenges from Victor in a consistent way – that is, from the same commitment of the cards.
The protocol
Here is the setup. Both Peggy and Victor know a Sudoku puzzle, and Peggy also knows its solution.
Step 1. Peggy creates a random new puzzle and its solution, by creating a random permutation of the numbers 1 through 9.
Step 2. Peggy commits to each cell of the puzzle. (Remember that each commitment needs its own one-time randomness!) She sends all 81 commitments to Victor.
Step 3. Victor requests that Peggy do one of the following.
- Open all 9 commitments on a row of Victor’s choice.
- Open all 9 commitments on a column of Victor’s choice.
- Open all 9 commitments on a grid of Victor’s choice.
- Open all of the public (yellow) values and share the permutation \(M\) that links the original puzzle with the permuted puzzle.
Note that there are a total of 28 possible actions that Victor can request here.
Step 4. Peggy performs the requested action by opening the commitments to the relevant cells, but no others.
Victor then checks that the commitments satisfy the desired property.
- If a row, column, or grid was opened: check that the numbers are 1 through 9 in some order.
- If the public values and \(M\) are opened, check that the opened puzzle really is a permuted version of the original (public) puzzle.
If so, he outputs Accept. Otherwise he outputs Reject.
The analysis
Does this proof satisfy the three criteria of a zero knowledge proof? Let’s check.
Completeness is the easiest property to think about. If Peggy is telling the truth, then her permuted and committed Sudoku puzzle will be correct. Hence, it will satisfy any of the 28 actions that Victor could request.
Soundness is a bit more complicated to reason about. Remember that soundness is about catching a faulty prover.
If the statement \(x\) is false and Victor is honest, then it is infeasible for any prover Peggy (even a malicious/faulty one) to deceive Victor. That is, Victor will output False, except maybe with some probability \(\varepsilon\) of making an error and reaching a decision of True instead.
If Peggy is lying and the Sudoku puzzle actually has no solution, then:
Peggy’s permuted & committed puzzle has to be wrong somewhere. (After all: if it satisfies the rules for all rows, columns, and grids and connects to the real statement \(x\), then it is a valid Sudoku solution!)
We don’t know which of the 28 conditions Peggy has violated, but it has to be at least one of them.
Hence, if the statement \(x\) is false, then Victor will catch Peggy with at least probability \(\frac{1}{28}\); or in other words, Peggy will get away with cheating with probability at most \(\varepsilon = \frac{27}{28} = 0.9643\).
That’s… actually not very satisfying.
Question. How can we reduce the soundness error?
Answer.
We can amplify the soundness via repetition. Just run the proof many times, either in sequence or in parallel. Each time, Peggy chooses a new permutation \(M\) and new commitments for each cell. And each time, Victor has a chance to catch Peggy in a lie.
If we repeat the protocol \(k\) times, then Peggy gets away with cheating with probability at most \((27/28)^k\). This probability vanishes to 0 exponentially fast in \(k\). For instance if we choose \(k = 2440\), then the probability of cheating on all repetitions is less than \(1/2^{128}\), which is our usual crypto standard for “infeasible.”
Admittedly, this requires that Peggy and Victor construct, exchange, and open a lot of Sudoku puzzles. Oh well. At least computing power and network communication are cheap nowadays!
Zero knowledgeness is also a subtle point to reason about. Remember that our goal is to construct a simulator whose actions look identical to the real prover Peggy’s work in the real world.
| Simulator\((x)\) | Verifier Victor\((x)\) | |
|---|---|---|
|
|
\(\begin{array}{c} \underset{\longleftarrow}{\pi_\text{Fake}} \\ \longrightarrow \\ \vdots \\ \longrightarrow \end{array}\) |
|
| output: Accept or Reject |
But also: the simulator isn’t real; it’s just a figment of Victor’s mind. And as a result, the simulator already “knows” the decisions that Victor will take – specifically, which of the 28 checks Victor will choose to test Peggy on.
As a result, the simulator (who doesn’t know the Sudoku solution \(w\)) can interact with Victor by using a fake puzzle that is only correct on the opened commitments, but nowhere else.
To make this claim rigorous, let’s change the protocol slightly by adding a new round of interaction at the start of the zero knowledge proof.
- Victor commits to his choice of action in step 3 below.
- Peggy sends all 81 commitments to the permuted puzzle to Victor.
- Victor opens his commitment from step 1 and requests that Peggy do one of 28 specified actions.
- Peggy performs the requested action by opening the commitments to the relevant cells. Victor checks that they satisfy the desired property.
Also when we say that the simulator and Victor are the same party, what we mean formally is that they are both just computer programs that are controlled by the same entity. We’ll see in a second how to use this property.
Here’s how the simulator works.
Since the simulator doesn’t know the real solution \(w\), it makes up a random Sudoku puzzle that has no connection to reality.
Next, the simulator interacts with Victor to perform steps 1, 2, and 3 of the protocol. So far, the simulator has only sent commitments to the fake puzzle, but commitments are hiding so Victor cannot tell that the simulator is using a fake puzzle. (Victor would find out if we continued on to step 4, though.)
From step 3 of the proof, the simulator has now learned which action Victor will use as his test. Now the simulator rewinds Victor’s state back to the end of step 1, creates a new puzzle that is correct on the desired row/column/grid/public values, and completes the rest of the proof in the same way as the honest prover would.
That’s it! This “rewinding” trick is what makes the analysis work. This is how we formalize the intuitive claim from before that:
It isn’t really the cards themselves that convince Victor that the proof is true. Instead what convinces Victor is that Peggy already committed to the cards beforehand (i.e., placed them facedown and cannot change them later).