Zero Knowledge Proofs

What is information? What is knowledge?

  • Alice sends to Bob the string 0n
  • Alice sends to Bob the string s=3.14159, n bits
  • Alice sends to Bob the encryption of s 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 (Gen,Enc,Dec) is zero-knowledge encryption scheme if there exists a PPT simulator algorithm S such that NUPPT D, a negligible function ϵ(n), such that m{0,1}n it holds that D distinguishes the following distributions with probability at most ϵ(n):

  • {kGen(1n):Enck(m)}
  • {S(1n)}

Discuss: what if we allow S to take exponential time (in n)?

Theorem:

(Gen,Enc,Dec) 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 (A,B) is the computation performed by (A,B) through rounds, where the sending tape of A is the receiving tape of B and vice versa. In each round, only one ITM is active.

Transcript: all messages sent by both (A,B) during the execution of the protocol.

Random execution: both A and B can be randomized and takes randomness (ie random tapes) ra and rb correspondingly.

Outputs: each ITM in the protocol may halt and write to its output tape. We denote outA[A(xa,za,ra)B(xb,zb,rb)] as the output of A when the inputs xa,xb, aux inputs za,zb, and randomness ra,rb are given to A and B correspondingly. We similarly denote outB[A(xa,za,ra)B(xb,zb,rb)] as the output of B. We analogously use the random varialbe outA[A(xa,za)B(xb,zb)] as the output of A (and outB similarly) if the random tapes are randomized.

Views: fixing inputs xa,xb, aux inputs za,zb, and randomness ra,rb, the transcript of the execution between A(xa,za,ra) and B(xb,zb,rb) is fixed. We denote the view of A as viewB[A(xa,za,ra)B(xb,zb,rb)], which consists of

  • xa,za,ra
  • the receiving tape (for all rounds of communication)

Similarly, if the ITMs are randomized, the transcript is a random variable (depends on ra,rb), and we write the random variable viewA[A(xa,za)B(xb,zb)]. The view of B is denoted as viewB[A(xa,za)B(xb,zb)] symmetrically.

Definition: Interactive Proof

A pair of ITMS (P,V) is an interactive proof system for a language L if V is a PPT machine and the follwing properties hold.

  1. (Completeness) For every xL, there exists a witness string w{0,1} such that for every auxiliary string z:

    Pr[outV[P(x,w)V(x,z)]=1]=1
  2. (Soundness) There exists some negligible function ϵ such that for all xL and for all (adversarial) prover algorithms P, and all auxiliary strings z{0,1},

    Pr[outV[P(x)V(x,z)]=0]>1ϵ(|x|)

Notice: both the honest P and the malicious P are allowed to be unbounded and non-uniform. That is, inefficient prover.

Complexity: The class of languages having an interactive proofs is denoted IP. It is direct to see that NPIP as V is PPT (simply sending the witness w to V). It is proved that IP=PSPACE.

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 LNP, the IP is simply sending the witness w to V.

In cryptography, we consider to hide the witness from an adversarial V. Following the intuition of zero-knowledge, V shall be able to simulate its view using its own input.

Definition

Definition: Honest Verifier Zero-Knowledge

Let (P,V) be an efficient interactive proof for the language LNP with witness relation RL. (P,V) is said to be honest verifier zero-knowledge if there exists a PPT simulator S such that for every xL,wRL(x),z{0,1}, the following distributions are computationally indistinguishable.

  • {viewV[P(x,w)V(x,z)]}n
  • {S(x,z)}n

where n:=|x| is the problem size.

Note: the auxiliary info z denotes any a-priori information that is given to V; that is, if V knew w, then S needs w as well to simulate the view.

The above definition supposes the verifier follows the protocol (provided as the algorithm V). This is unsatisfactory, and we go for a stronger definition that considers any efficient adversary A. However, the view then depends on A, and we need the simulator that depends on A as well. Notice that the quantifier of S differs below.

Definition: Zero-Knowledge

Let (P,V) be an efficient interactive proof for the language LNP with witness relation RL. (P,V) is said to be zero-knowledge if for every PPT adversary V, there exists a PPT simulator S such that for every xL,wRL(x),z{0,1}, the following distributions are computationally indistinguishable.

  • {viewV[P(x,w)V(x,z)]}n
  • {S(x,z)}n

where n:=|x| is the problem size.

Note that here only consider PPT adversaries V (as opposed to non-uniform PPT adversaries). This only makes our definition stronger: V can anyway receive any non-uniform “advice” as its auxiliary input; in contrast, we can now require that the simulator S is only PPT but is also given the auxiliary input of V. Thus, our definition says that even if V 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 viewV with outV. (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: P gives it to V, then P can not change the content while V knows nothing about the content, and then P can open it later to V.

Definition: Commitment

A polynomial-time machine Com is called a commitment scheme if there exists some polynomial () such that the following two properties hold:

  1. (Binding): For all nN and all v0v1{0,1}n, r0,r1{0,1}(n) it holds that Com(v0,r0)Com(v1,r1).
  2. (Hiding): For every v0,v1{0,1}n, the following distributions are computationally indistinguishable:

    • {r{0,1}(n):Com(v0,r)}
    • {r{0,1}(n):Com(v1,r)}

Notice: in the definition, the binding is perfect, which means that no adversary can open Com(v,r) to vv by providing any r (even the adversary is unbounded). In contrast, the hiding is only computational where an exponential time adversary may find v given only Com(v,r).

Discuss: the hiding property is similar to encryption, where Com(v,r) might be thought as Encr(v). 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 c can be decrypted to different values when different decryption keys are used.

Theorem:

If one-way permutations exist, then commitment schemes exist.

Let f be a OWP and h be its hard-core predicate. Let Com(b,r):=(f(r),bh(r)). 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: G=(V,E) where |V|=n,|E|=m

Prover input: Witness w=(c0,c1,...,cm)

P  VLet π be a random permutation over {1,2,3}. For each i[1,n], P sends a commitment to the color ci:=π(ci)
P  VV sends a randomly chosen edge (i,j)E
P  VP opens commitments ci and cj.
 VV rejects the proof if and only if ci=cj (continue o.w.)
P,VRepeat the procedure n|E| times.

Theorem:

Assume Com 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 G is not 3-colorable, then there exists (i,j) such that ci=cj, and then by binding, any adversarial P must open the commitments ci and cj to the same ci=cj when V chose (i,j), which happens w.p. 1/|E|. By (11/x)xe1, it follows that all n|E| repetition passes w.p.

(11|E|)n|E|en.

To prove ZK, the intuition is that P reveals only the colors of two random vertices, and that the hiding of Com guarantees that other vertices are hidden. Formally, we construct the following simulator.

Simulator for graph 3-coloring, S(G,z):

  1. Pick a random edge (s,t)E and pick random colors cs,ct{1,2,3},csct. Let ck=1 for all other k[n]{s,t}.
  2. Commit to ci for all i and send them to V(G,z). Let (i,j) be the message of V.
  3. If (i,j)=(s,t) then open cs,ct and output the view of V. Otherwise, restart the process from picking random (s,t) again, but for at most n|E| times.
  4. If the simulation has not been successful after n|E| repetitions, output fail .

To argue why S outputs an indistinguishable view, consider hybrid simulators:

  • S: it additionally takes input the witness w and performs similar to S, but it commits to π(w(v)) for v{s,t} and random π
  • P: it is similar to P (which takes w), but it takes z and picks (s,t) and restarts if the edge (i,j) chosen by V is not (s,t) (as in S)

Conditioning on the output of P is not , we have that

viewV[P(G,w)V(G,z)]P(G,w,z),

where denotes identical distribution. Since the event happens w.p. en, the two distributions are statistically close. We also have that S(G,z,w)S(G,z), and it suffices to show that SP.

To see that P(G,z,w) and S(G,z,w) are computationally indistinguishable, we rely on the hiding of Com and a sequence of hybrids S0,S1,,SR where R=n|E|:

  • In Sr, the first r “restarts” follow P but then the remaining “restarts” follow S.

Hence, we have S0=S and SR=P. We define further define for each r[R] the subsequence Sr,0,,Sr,n:

  • In Sr,k, the commitments are identical to Sr except for the r-th restart that the first k commitments uses the coloring from w but the remaining commitments uses 1.

We have Sr,n=Sr and Sr,0=Sr1.

Now we are ready for the reduction. Assume for contradiction, there exists NUPPT D, polynomial p such that for infinitely many nN, D distinguishes between S0=S and SR=P w.p. at least 1/p(n). Then, we can construct an adversary A that breaks the hiding of Com:

  1. Sample (r,k)[R]×[n]
  2. Get from input a commitment c such that either c=Com(1,) or c=Com(π(w(vk)),)
  3. Compute all other commitments according to the coloring of Sr,k
  4. Run V as per Sr,k using the computed commitments including c to obtain the resulting view
  5. Run D to distinguish view and output the output of D

It suffices to observe that if c=Com(1) then A runs V identical to Sr,k, and if c=Com(π(w(vk))) then A runs V identical to Sr,k1. Hence, the probability of distinguishing c is at least 1/n2|E|p(n), contradicting the binding of Com.

Notice In the above S, we try to guess an edge (s,t) before we commit to it, and then we just retry (“restart”) when the guess is inconsistent with (i,j) from V. 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 S could be longer and become expected PPT in the Security Definition (i.e., we can relax S 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 (GC) is NP-complete, we can reduce from GC to any language LNP. That is, there exists a deterministic polynomial time reduction R such that for any string x, xL if and only if x=R(x)GC; moreover, w is a witness of xL if and only if w=R(x,w) is a witness of xGC.

Hence we can construct ZK proof for any LNP from GC.

Protocol: ZKP for LNP.

Common input: x

Prover input: Witness w

PLet G:=R(x), let w=R(x,w)
VLet G:=R(x)
P  VRun the ZKP protocol (P,V) of graph 3-coloring, i.e., P(G,w)V(G)
VV rejects the proof if and only if V 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 k 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 pk on S and the secrete key sk on C. To identify C, S asks C to sign a message and then verifies the 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. Namely, given pk and message m from S, let L be the language:

  • (a,b) such that Verpk(Signa(m;b)) output Accept.

Clearly LNP and C has the witness (sk,r). Hence, C can convince S that she can sign m but S learned nothing more than (pk,m). 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.