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
Theorem:
is secure if and only if it is zero-knowledge.
See [Ps, Sec 4.2] for proof.
Interactive Proofs
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
Transcript: all messages sent by both
Random execution: both
Outputs: each ITM in the protocol may halt and write to its output tape. We denote
Views: fixing inputs
- the receiving tape (for all rounds of communication)
Similarly, if the ITMs are randomized, the transcript is a random variable (depends on
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
Complexity: The class of languages having an interactive proofs is denoted
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
In cryptography, we consider to hide the witness from an adversarial
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
The above definition supposes the verifier follows the protocol (provided as the algorithm
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
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:
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
Discuss: the hiding property is similar to encryption, where
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
Any Language in class NP
Recall that since graph 3-coloring (
Hence we can construct ZK proof for any
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
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
A better way is to store the public key
Using ZKP, C can prove the identity to S without letting S having the signature. Namely, given
such that output Accept.
Clearly
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.