\newcommand{\Gen}{\mathsf{Gen}} \newcommand{\Enc}{\mathsf{Enc}} \newcommand{\Dec}{\mathsf{Dec}} \newcommand{\Com}{\mathsf{Com}} \newcommand{\out}{\mathsf{out}} \newcommand{\view}{\mathsf{view}}

Zero Knowledge Proofs

What is information? What is knowledge?

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

  • {kGen(1n):Enck(m)}\set{k \to \Gen(1^n) : \Enc_k(m)}
  • {S(1n)}\set{S(1^n)}

Discuss: what if we allow SS to take exponential time (in nn)?

Theorem:

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

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

Random execution: both AA and BB can be randomized and takes randomness (ie random tapes) rar_a and rbr_b 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)]\out_A[A(x_a, z_a, r_a) \leftrightarrow B(x_b, z_b, r_b)] as the output of AA when the inputs xa,xbx_a, x_b, aux inputs za,zbz_a, z_b, and randomness ra,rbr_a, r_b are given to AA and BB correspondingly. We similarly denote outB[A(xa,za,ra)B(xb,zb,rb)]\out_B[A(x_a, z_a, r_a) \leftrightarrow B(x_b, z_b, r_b)] as the output of BB. We analogously use the random varialbe outA[A(xa,za)B(xb,zb)]\out_A[A(x_a, z_a) \leftrightarrow B(x_b, z_b)] as the output of AA (and outB\out_B similarly) if the random tapes are randomized.

Views: fixing inputs xa,xbx_a, x_b, aux inputs za,zbz_a, z_b, and randomness ra,rbr_a, r_b, the transcript of the execution between A(xa,za,ra)A(x_a, z_a, r_a) and B(xb,zb,rb)B(x_b, z_b, r_b) is fixed. We denote the view of AA as viewB[A(xa,za,ra)B(xb,zb,rb)]\view_B[A(x_a, z_a, r_a) \leftrightarrow B(x_b, z_b, r_b)], which consists of

  • xa,za,rax_a, z_a, r_a
  • the receiving tape (for all rounds of communication)

Similarly, if the ITMs are randomized, the transcript is a random variable (depends on ra,rbr_a, r_b), and we write the random variable viewA[A(xa,za)B(xb,zb)]\view_A[A(x_a, z_a) \leftrightarrow B(x_b, z_b)]. The view of BB is denoted as viewB[A(xa,za)B(xb,zb)]\view_B[A(x_a, z_a) \leftrightarrow B(x_b, z_b)] symmetrically.

Definition: Interactive Proof

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

  1. (Completeness) For every xLx \in L, there exists a witness string w{0,1}w \in \bit^\ast such that for every auxiliary string zz:

    Pr[outV[P(x,w)V(x,z)]=1]=1\Pr \left[\out_V [P(x, w) \leftrightarrow V(x, z)] = 1 \right] = 1
  2. (Soundness) There exists some negligible function ϵ\eps such that for all xLx \notin L and for all (adversarial) prover algorithms PP^\ast, and all auxiliary strings z{0,1}z \in \bit^\ast,

    Pr[outV[P(x)V(x,z)]=0]>1ϵ(x)\Pr \left[\out_V [P^\ast(x) \leftrightarrow V(x, z)] = 0 \right] \gt 1 − \eps(|x|)

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

Complexity: The class of languages having an interactive proofs is denoted IPIP. It is direct to see that NPIPNP \subset IP as VV is PPT (simply sending the witness ww to VV). It is proved that IP=PSPACEIP = 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 LNPL \in NP, the IP is simply sending the witness ww to VV.

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

Definition

Definition: Honest Verifier Zero-Knowledge

Let (P,V)(P, V) be an efficient interactive proof for the language LNPL \in NP with witness relation RLR_L. (P,V)(P, V) is said to be honest verifier zero-knowledge if there exists a PPT simulator SS such that for every xL,wRL(x),z{0,1}x \in L, w \in R_L(x), z \in \bit^\ast, the following distributions are computationally indistinguishable.

  • {viewV[P(x,w)V(x,z)]}n\set{\view_V [P(x, w) \leftrightarrow V(x, z)]}_n
  • {S(x,z)}n\set{S(x, z)}_n

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

Note: the auxiliary info zz denotes any a-priori information that is given to VV; that is, if VV knew ww, then SS needs ww as well to simulate the view.

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

Definition: Zero-Knowledge

Let (P,V)(P, V) be an efficient interactive proof for the language LNPL \in NP with witness relation RLR_L. (P,V)(P, V) is said to be zero-knowledge if for every PPT adversary VV^\ast, there exists a PPT simulator SS such that for every xL,wRL(x),z{0,1}x \in L, w \in R_L(x), z \in \bit^\ast, the following distributions are computationally indistinguishable.

  • {viewV[P(x,w)V(x,z)]}n\set{\view_{V^\ast} [P(x, w) \leftrightarrow V^*(x, z)]}_n
  • {S(x,z)}n\set{S(x, z)}_n

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

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

Definition: Commitment

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

  1. (Binding): For all nNn \in \N and all v0v1{0,1}nv_0 \neq v_1 \in \bit^n, r0,r1{0,1}(n)r_0, r_1 \in \bit^{\ell(n)} it holds that Com(v0,r0)Com(v1,r1)\Com(v_0, r_0) \neq \Com(v_1, r_1).
  2. (Hiding): For every v0,v1{0,1}nv_0, v_1 \in \bit^n, the following distributions are computationally indistinguishable:

    • {r{0,1}(n):Com(v0,r)}\set{r \gets \bit^{\ell(n)} : \Com(v_0, r)}
    • {r{0,1}(n):Com(v1,r)}\set{r \gets \bit^{\ell(n)} : \Com(v_1, r)}

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

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

Theorem:

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

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

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

P  VP ~\to ~ VLet π\pi be a random permutation over {1,2,3}\set{1, 2, 3}. For each i[1,n]i \in [1, n], PP sends a commitment to the color ci:=π(ci)c'_i := \pi(c_i)
P  VP~\gets ~VVV sends a randomly chosen edge (i,j)E(i, j) \in E
P  VP ~\to ~ VPP opens commitments cic'_i and cjc'_j.
 V\quad\quad~ VVV rejects the proof if and only if ci=cjc'_i = c'_j (continue o.w.)
P,VP, VRepeat the procedure nEn \vert E \vert times.

Theorem:

Assume Com\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 GG is not 3-colorable, then there exists (i,j)(i,j) such that ci=cjc_i = c_j, and then by binding, any adversarial PP^\ast must open the commitments cic'_i and cjc'_j to the same ci=cjc_i = c_j when VV^\ast chose (i,j)(i,j), which happens w.p. 1/E\ge 1/|E|. By (11/x)xe1(1 - 1/x)^x \le e^{-1}, it follows that all nEn|E| repetition passes w.p.

(11E)nEen.(1 - \frac{1}{|E|})^{n |E|} \le e^{-n}.

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

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

  1. Pick a random edge (s,t)E(s, t) \in E and pick random colors cs,ct{1,2,3},csctc'_s, c'_t \in \set{1, 2, 3}, c'_s \neq c'_t. Let ck=1c'_k = 1 for all other k[n]{s,t}k \in [n] \setminus \set{s,t}.
  2. Commit to cic'_i for all ii and send them to V(G,z)V^\ast(G, z). Let (i,j)(i,j) be the message of VV^\ast.
  3. If (i,j)=(s,t)(i,j) = (s,t) then open cs,ctc'_s, c'_t and output the view of VV^\ast. Otherwise, restart the process from picking random (s,t)(s,t) again, but for at most nEn|E| times.
  4. If the simulation has not been successful after nEn|E| repetitions, output fail \bot.

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

  • SS': it additionally takes input the witness ww and performs similar to SS, but it commits to π(w(v))\pi(w(v)) for v{s,t}v \in \set{s,t} and random π\pi
  • PP': it is similar to PP (which takes ww), but it takes zz and picks (s,t)(s,t) and restarts if the edge (i,j)(i,j) chosen by VV^\ast is not (s,t)(s,t) (as in SS)

Conditioning on the output of PP' is not \bot, we have that

viewV[P(G,w)V(G,z)]P(G,w,z),\view_{V^\ast}\brackets{ P(G, w) \leftrightarrow V^\ast(G, z) } \equiv P'(G, w, z),

where \equiv denotes identical distribution. Since the \bot event happens w.p. en\le e^{-n}, the two distributions are statistically close. We also have that S(G,z,w)S(G,z)S'(G,z,w) \equiv S(G,z), and it suffices to show that SPS' \approx P'.

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

  • In SrS_r, the first rr “restarts” follow PP' but then the remaining “restarts” follow SS'.

Hence, we have S0=SS_0 = S' and SR=PS_R = P'. We define further define for each r[R]r \in [R] the subsequence Sr,0,...,Sr,nS_{r,0}, ..., S_{r,n}:

  • In Sr,kS_{r,k}, the commitments are identical to SrS_r except for the rr-th restart that the first kk commitments uses the coloring from ww but the remaining commitments uses 11.

We have Sr,n=SrS_{r,n} = S_r and Sr,0=Sr1S_{r,0} = S_{r-1}.

Now we are ready for the reduction. Assume for contradiction, there exists NUPPT DD, polynomial pp such that for infinitely many nNn\in\N, DD distinguishes between S0=SS_0 = S' and SR=PS_R = P' w.p. at least 1/p(n)1/p(n). Then, we can construct an adversary AA that breaks the hiding of Com\Com:

  1. Sample (r,k)[R]×[n](r,k) \gets [R] \times [n]
  2. Get from input a commitment cc such that either c=Com(1,...)c = \Com(1, ...) or c=Com(π(w(vk)),...)c = \Com(\pi(w(v_k)), ...)
  3. Compute all other commitments according to the coloring of Sr,kS_{r,k}
  4. Run VV^\ast as per Sr,kS_{r,k} using the computed commitments including cc to obtain the resulting view\view
  5. Run DD to distinguish view\view and output the output of DD

It suffices to observe that if c=Com(1)c = \Com(1) then AA runs VV^\ast identical to Sr,kS_{r,k}, and if c=Com(π(w(vk)))c = \Com(\pi(w(v_k))) then AA runs VV^\ast identical to Sr,k1S_{r,k-1}. Hence, the probability of distinguishing cc is at least 1/n2Ep(n)\ge 1/n^2|E|p(n), contradicting the binding of Com\Com.

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

Hence we can construct ZK proof for any LNPL \in NP from GCGC.

Protocol: ZKP for LNPL \in NP.

Common input: xx

Prover input: Witness ww

PPLet G:=R(x)G' := R(x), let w=R(x,w)w' = R(x,w)
V\quad\qquad VLet G:=R(x)G' := R(x)
P  VP ~\leftrightarrow ~ VRun the ZKP protocol (P,V)(P',V') of graph 3-coloring, i.e., P(G,w)V(G)P'(G', w') \leftrightarrow V'(G')
V\quad\qquad VVV rejects the proof if and only if VV' rejects

Remark: It might be confusing: if the language LNPL \in NP is easy to solve, the polynomial-time verifier VV^* can find the witness efficiently, then how could we have zero-knowledge proof for xLx\in L? This is indeed captured in the ZK definition—if something is computable by only V(x)V^*(x) (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 NPNP 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 kk 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 pkpk on S and the secrete key sksk 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 M\cM be the message space of the above signature scheme. Then, define the language LL to be the following:

L:={pk:pk is a valid output from (pk,sk)Gen(1n;r)}.L := \set{ \pk : \pk \text{ is a valid output from } (\pk, \sk)\gets \Gen(1^n; r)}.

Recall that rr is the randomness used by Gen\Gen. Clearly, LNPL \in NP because for any pkL\pk \in L, there exists corresponding w=(sk,r)w = (\sk,r) as the witness of pk\pk.

Hence, C can convince S that she has the signing key sk\sk but S learned nothing more than pk\pk. 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.