Zero Knowledge Proofs
What is information? What is knowledge?
- Alice sends to Bob the string
- Alice sends to Bob the string , bits
- Alice sends to Bob the encryption of without a key
Shannon’s information theory is relevant, but here we consider “knowledge” (instead of information) in the context of computational aspects.
Example: the encrypted message is zero-knowledge to the adversary who has no key because the encryption can be simulated by the adversary itself!
Definition: Zero-Knowledge Encryption
A private-key encryption scheme is zero-knowledge encryption scheme if there exists a PPT simulator algorithm such that NUPPT , a negligible function , such that it holds that distinguishes the following distributions with probability at most :
Discuss: what if we allow to take exponential time (in )?
Theorem:
is secure if and only if it is zero-knowledge.
See [Ps, Sec 4.2] for proof.
Interactive Proofs
What is a proof? Historically, a proof separates “calculation” and mathematics. For computers, mathematical proofs are nothing more than bit strings. Still, we human want a good proof to satisfy some propoerties.
- There is a well-defined statement to be proved.
- If the statement is true, then a good proof shall convice “any” reader, i.e., verifiable.
- Else, the statement is false, then ideally there shall be no verifiable proof.
We consider interactions between interactive Turing machines (ITM) that run in multiple rounds. Each ITM has the following tapes:
- Input tape, read only
- Auxiliary input tape, read only (we will see later why it is needed)
- Working tape, allowing both read/write
- Sending tape, write only
- Receiving tape, read only
- Output tape, write only
In each round, the ITM reads from input + aux + receive tapes, performs computation on working tape, and then writes to sending / output tape.
A protocol between two ITMs is the computation performed by through rounds, where the sending tape of is the receiving tape of and vice versa. In each round, only one ITM is active.
Transcript: all messages sent by both during the execution of the protocol.
Random execution: both and can be randomized and takes randomness (ie random tapes) and correspondingly.
Outputs: each ITM in the protocol may halt and write to its output tape. We denote as the output of when the inputs , aux inputs , and randomness are given to and correspondingly. We similarly denote as the output of . We analogously use the random varialbe as the output of (and similarly) if the random tapes are randomized.
Views: fixing inputs , aux inputs , and randomness , the transcript of the execution between and is fixed. We denote the view of as , which consists of
- the receiving tape (for all rounds of communication)
Similarly, if the ITMs are randomized, the transcript is a random variable (depends on ), and we write the random variable . The view of is denoted as symmetrically.
Definition: Interactive Proof
A pair of ITMS is an interactive proof system for a language if is a PPT machine and the follwing properties hold.
(Completeness) For every , there exists a witness string such that for every auxiliary string :
(Soundness) There exists some negligible function such that for all and for all (adversarial) prover algorithms , and all auxiliary strings ,
Notice: both the honest and the malicious are allowed to be unbounded and non-uniform. That is, inefficient prover.
Complexity: The class of languages having an interactive proofs is denoted . It is direct to see that as is PPT (simply sending the witness to ). It is proved that .
It is natural to consider IP in crypto setting because one party may want to achieve more than what’s given by the completeness.
Zero-Knowledge Proofs
We first require the honest prover to be efficient, i.e., PPT ITM. For any , the IP is simply sending the witness to .
In cryptography, we consider to hide the witness from an adversarial . Following the intuition of zero-knowledge, shall be able to simulate its view using its own input.
Definition
Definition: Honest Verifier Zero-Knowledge
Let be an efficient interactive proof for the language with witness relation . is said to be honest verifier zero-knowledge if there exists a PPT simulator such that for every , the following distributions are computationally indistinguishable.
where is the problem size.
Note: the auxiliary info denotes any a-priori information that is given to ; that is, if knew , then needs as well to simulate the view.
The above definition supposes the verifier follows the protocol (provided as the algorithm ). This is unsatisfactory, and we go for a stronger definition that considers any efficient adversary . However, the view then depends on , and we need the simulator that depends on as well. Notice that the quantifier of differs below.
Definition: Zero-Knowledge
Let be an efficient interactive proof for the language with witness relation . is said to be zero-knowledge if for every PPT adversary , there exists a PPT simulator such that for every , the following distributions are computationally indistinguishable.
where is the problem size.
Note that here only consider PPT adversaries (as opposed to non-uniform PPT adversaries). This only makes our definition stronger: can anyway receive any non-uniform “advice” as its auxiliary input; in contrast, we can now require that the simulator is only PPT but is also given the auxiliary input of . Thus, our definition says that even if is non-uniform, the simulator only needs to get the same non-uniform advice to produce its view.
[Ps, p122]
Alternatively, we can directly replace with . (The proof is left as an exercise)
Commitment
We will propose a ZKP for the NP-complete language, graph 3-coloring. The protocol will use commitments that can be thought as a physical locked box: gives it to , then can not change the content while knows nothing about the content, and then can open it later to .
Definition: Commitment
A polynomial-time machine is called a commitment scheme if there exists some polynomial such that the following two properties hold:
- (Binding): For all and all , it holds that .
(Hiding): For every , the following distributions are computationally indistinguishable:
Notice: in the definition, the binding is perfect, which means that no adversary can open to by providing any (even the adversary is unbounded). In contrast, the hiding is only computational where an exponential time adversary may find given only .
Discuss: the hiding property is similar to encryption, where might be thought as . That could be a good intuition when we want to use hiding later in the security proof. However, binding is not a property from typical encryption schemes: for many encryption schemes, the same ciphertext can be decrypted to different values when different decryption keys are used.
Theorem:
If one-way permutations exist, then commitment schemes exist.
Let be a OWP and be its hard-core predicate. Let . Binding is direct from permutation. Hiding is simple by the definition of hard-core predicate.
Note: there are also constructions of commitment from OWF.
Graph 3-Coloring
Protocol: ZKP for Graph 3-Coloring
Common input: where
Prover input: Witness
Let be a random permutation over . For each , sends a commitment to the color sends a randomly chosen edge opens commitments and . rejects the proof if and only if (continue o.w.) Repeat the procedure times.
Theorem:
Assume is a secure commitment scheme. The above protocol is a zero-knowledge protocol for the language of 3-colorable graphs.
The completeness is direct. The soundness follows by the binding property as below. If is not 3-colorable, then there exists such that , and then by binding, any adversarial must open the commitments and to the same when chose , which happens w.p. . By , it follows that all repetition passes w.p.
To prove ZK, the intuition is that reveals only the colors of two random vertices, and that the hiding of guarantees that other vertices are hidden. Formally, we construct the following simulator.
Simulator for graph 3-coloring, :
- Pick a random edge and pick random colors . Let for all other .
- Commit to for all and send them to . Let be the message of .
- If then open and output the view of . Otherwise, restart the process from picking random again, but for at most times.
- If the simulation has not been successful after repetitions, output fail .
To argue why outputs an indistinguishable view, consider hybrid simulators:
- : it additionally takes input the witness and performs similar to , but it commits to for and random
- : it is similar to (which takes ), but it takes and picks and restarts if the edge chosen by is not (as in )
Conditioning on the output of is not , we have that
where denotes identical distribution. Since the event happens w.p. , the two distributions are statistically close. We also have that , and it suffices to show that .
To see that and are computationally indistinguishable, we rely on the hiding of and a sequence of hybrids where :
- In , the first “restarts” follow but then the remaining “restarts” follow .
Hence, we have and . We define further define for each the subsequence :
- In , the commitments are identical to except for the -th restart that the first commitments uses the coloring from but the remaining commitments uses .
We have and .
Now we are ready for the reduction. Assume for contradiction, there exists NUPPT , polynomial such that for infinitely many , distinguishes between and w.p. at least . Then, we can construct an adversary that breaks the hiding of :
- Sample
- Get from input a commitment such that either or
- Compute all other commitments according to the coloring of
- Run as per using the computed commitments including to obtain the resulting
- Run to distinguish and output the output of
It suffices to observe that if then runs identical to , and if then runs identical to . Hence, the probability of distinguishing is at least , contradicting the binding of .
Notice In the above , we try to guess an edge before we commit to it, and then we just retry (“restart”) when the guess is inconsistent with from . The “restart” differs from the reductions in the previous sections of this course, but it is a generic technique in the security proof of ZKP. Due to such guess, the running time of could be longer and become expected PPT in the Security Definition (i.e., we can relax to be “Las Vegas” PPT and greatly facilitate the construction of ZKP, [Ps, p121]).
Any Language in class NP
Recall that since graph 3-coloring () is NP-complete, we can reduce from any language to . That is, there exists a deterministic polynomial time reduction such that for any string , if and only if ; moreover, is a witness of if and only if is a witness of .
Hence we can construct ZK proof for any from .
Protocol: ZKP for .
Common input:
Prover input: Witness
Let , let Let Run the ZKP protocol of graph 3-coloring, i.e., rejects the proof if and only if rejects
Remark: It might be confusing: if the language is easy to solve, the polynomial-time verifier can find the witness efficiently, then how could we have zero-knowledge proof for ? This is indeed captured in the ZK definition—if something is computable by only (and the simulator), then the same thing is allowed in the real ZK protocol. Indeed in many crypto applications, we need ZKP for some language that is in but is probablity not NP-complete (see the next example).
Ref: The ZKP for 3-coloring is proposed in the seminal work by Goldreich, Micali, and Wigderson [GMW]. Just in this year (2024), Avi Wigderson wins A.M. Turing Award for his contribution to the theory of computation. Read the article of Quanta Magazine for his contribution (including ZKP and derandomization).
Application: Identification with Repudiation
Consider that a Client log-in to a remote Server. On Server side, a simple way to identify C is to share the same key between C and S (and then MAC). However, shared key is undesirable in the case S could be compromised.
A better way is to store the public key on S and the secrete key on C. To identify C, S asks C to sign a message and then verifies the signature, where the message shall be sampled randomly and non-repeating (so that no adversary can replay the same signature). This is good, but later S can prove to anyone that C has logged in by showing the signature, which is undesirable.
Using ZKP, C can prove the identity to S without letting S having the signature. Let be the message space of the above signature scheme. Then, define the language to be the following:
Recall that is the randomness used by . Clearly, because for any , there exists corresponding as the witness of .
Hence, C can convince S that she has the signing key but S learned nothing more than . Notice that if S wants to show the trace of C, C can deny because the view of S can totally be simulated by S itself.
Extended Material
Non-Interactive Zero-Knowledge proofs, also known as NIZK, consider the setting that the prover sends only one message to the verifier (and no message is sent from verifier). It typically requires that the prover and verifier share a Common Reference String (CRS) that is constructed by a trusted third party. Observe that in the above ZKP of Graph 3-Coloring, the verifer’s message is sampled uniformly and independent of the prover’s message. Hence, Fiat and Shamir suggest to have the prover sample the message, using CRS as a hash function so that the prover can not cheat; this is known as Fiat-Shamir heuristic, see Wikipedia for examples.
Alternatively, Feige, Lapidot, Shamir introduced Hidden-Bits Model and achieved NIZK, FLS 1999. It uses Hamiltonian Cycle as the NP-Complete language (which looks more natural than 3-Coloring in the construction); see Katz at Maryland and Garg at Berkeley for details.
In this section (and almost all ZK applications), we consider only computational ZK, which means that the adversarial verifier is computationally bounded (i.e., NUPPT). It is possible to extend the ZK even from unbounded verifier, and that is called statisticl ZKP (SZK). See the survey by Vadhan for the complexity class SZK.