Zero Knowledge Proofs
Introduction to Zero Knowledge Interactive Proofs
Dan Boneh, Shafi Goldwasser, Dawn Song, Justin Thaler, Yupeng Zhang

Classical Proofs…
...

… PrimeNumber Thm

a2+b2

a
b

2

ZKP MOOC

Proofs
ProverClaim

Verifier
accept/rejectproof

3

ZKP MOOC

Efficiently Verifiable Proofs (NP-proofs)

ProverClaim

Verifier
accept/rejectshort
proof
Works Hard

Polynomial Time

4ZKP MOOC

Efficiently Verifiable Proofs (NP-proofs)
Claim x

Prover P

Verifier Vw|w| = polynomial in |x|
Unbounded

Accepts x If
V(x,w)=1
Else reject
V takes time Polynomial in |x|5

ZKP MOOC

Claim: N is a product of 2 large primes
proof={p,q}
If N=pq, V accepts
Else V rejects

After interaction, V knows:
1) N is product of 2 primes2) The two primes p and q

6

ZKP MOOC

Claim: y is a quadratic residue mod N(i.e ∃𝑥 𝑖𝑛 𝑍!∗ s. t. y=x2 mod N)
Proof = 𝑥
If y=x2 mod N, V accepts
Else V rejects

After interaction, V knows:
1. y is a quadratic residue mod2. Square root of y (hard problem
equivalent to factoring N)

7

ZKP MOOC

Claim: the two graphs are isomorphic
1
2

10

8
3

1

2
6

5

7

5

9

6
8

3

10

4
4

9

7

After interaction, V knows:
1) G0 is isomorphic to G1
2) The isomorphism 𝝅

𝝅: 𝑵 → [𝑵],the isomorphism

8

Accept if ∀𝑖, 𝑗:
𝜋 𝑖 , 𝜋 𝑗 ∈ 𝐸! iff𝑖, 𝑗 ∈ 𝐸" .

ZKP MOOC

Efficiently Verifiable Proofs (NP-Languages)
Claim x

Prover P

Verifier V
Accepts x If
V(x,w)=1
Else rejectw

Works Hard

V Polynomial time

Def: A language 𝐿 is a set of binary strings x.
9

ZKP MOOC

Efficiently Verifiable Proofs (NP-Languages)
Claim xw

accept/reject

Def: ℒ is an 𝐍𝐏-language (or NP-decision problem), if there is a poly (|x|)
time verifier 𝑉 where• Completeness [True claims have (short) proofs].
if x ∈ ℒ, there is a poly(|𝐱|)-long witness w ∈ 0,1 ∗ s.t. 𝑉 𝑥, 𝑤 = 1.
• Soundness [False theorems have no proofs}.
if x ∉ ℒ, there is no witness. That is, for all w ∈ 0,1 ∗, 𝑉 𝑥, 𝑤 = 0.

10

ZKP MOOC

1982-1985: Is there any other way?

Theorem: y is a quadratic residue mod N
Proof= 𝒚 𝒎𝒐𝒅 𝑵 ∈ 𝒁∗𝑵

11

ZKP MOOC

Zero Knowledge Proofs: Yes
Main Idea:
Prove that
I could prove it
If I felt like it

12

ZKP MOOC

Zero Knowledge
Interactive Proofs

13

ZKP MOOC
Credit: Faithie/ShutterstockTwo New IngredientsInteractive and Probabilistic Proofs
Interaction: rather than passively “reading” proof, verifier engages
in a non-trivial interaction with the prover.

Randomness: verifier is randomized (tosses coins as a primitive
operation), and can err in accept/reject with small probability

14

ZKP MOOC

Interactive Proof Model
Claim/Theorem x

Prover

𝑎!
𝑞!
𝑎%
𝑞%
…

accept/reject

Verifier

Probabilistic
Polynomial-time (PPT)Comp. Unbounded15

ZKP MOOC

Here is the idea:
How to prove colors are different to a blind verifier

Claim: This page contains 2 colors

Sends resulting pageIf page is flipped
Set coin’=heads
Else coin’=tails

I guess you tossed coin’

16

Toss coin to decide if toflip page over or not
Heads flip, Tails don’t
If coin ¹ coin’,
reject, else accept

ZKP MOOC

Here is the idea:
How to prove colors are different to a blind verifier

Claim: This page contains 2 colors

Sends resulting pageIf page is flipped
Set coin’=heads
Else coin’=tails

I guess you tossed coin’

17

Toss coin to decide if toflip page over or not
Heads flip, Tails don’t
If coin ¹ coin’,
reject, else accept

ZKP MOOC

Interactive Proof for QR= 𝑁, 𝑦 : ∃𝑥 𝑠. 𝑡. 𝑦 = 𝑥2 𝑚𝑜𝑑 𝑁
Send s=r2 mod n and say

Chooserandom1≤ 𝑟 ≤ 𝑁s.t.
gcd(r,N)=1•

If I gave you square roots of both s and sy mod N you would
be convinced that the claim is true (but also know √𝑦 mod N)•

Instead, I will give you a square root of either s or of sy mod N
but you get to choose which!

Flip a b=

to choose

If b=1: send z=r
If b=0: send z=r √𝑦 mod N

18

Accepts
only ifz2=sy1-b mod N

ZKP MOOC

Interactive Proof for QR= 𝑁, 𝑦 : ∃𝑥 𝑠. 𝑡. 𝑦 = 𝑥2 𝑚𝑜𝑑 𝑁
Sends s=r2 mod n and says

Chooserandom1≤ 𝑟 ≤ 𝑁s.t.
gcd(r,N)=1•

If I gave you square roots of both s and sy mod N you would
be convinced that the claim is true (but also know √𝑦 mod N)•

Instead, I will give you a a square rot of s or of sy mod N but
you get to choose which!

Flip a b=

to choose

If b=1: send z=r
If b=0: send z=r √𝑦 mod N

19

Accepts
only ifz2=sy1-b mod N

ZKP MOOC

Interactive Proof for QR= 𝑁, 𝑦 : ∃𝑥 𝑠. 𝑡. 𝑦 = 𝑥2 𝑚𝑜𝑑 𝑁
Repeat 100 times
Send s=r2 mod n and says•

( 1/2 )100

If I gave you square roots of both s and sy mod N you would be
convinced that the claim is true (but also know √𝑦 mod N)

Chooserandom• Instead, I will give you a a square rot of s or of sy mod N but you
get to choose which!

s.t.
gcd(r,N)=1• The fact that I COULD (in principle) do both, should convince you

1≤ 𝑟 ≤ 𝑁

Flip a b=

to choose

If b=1: send z=r
If b=0: send z=r √𝑦 mod N

20

Accepts
only ifz2=sy1-b mod N

ZKP MOOC

What Made it possible?
§ The statement to be proven has many possible proofs ofwhich the prover chooses one at random.
§ Each such proof is made up of exactly 2 parts: seeing either
part on its own gives the verifier no knowledge; seeing bothparts imply 100% correctness.
§ Verifier chooses at random which of the two parts of theproof he wants the prover to give him. The ability of theprover to provide either part, convinces the verifier

21

ZKP MOOC

Definitions :of Zero Knowledge
Interactive Proofs

22

ZKP MOOC
Credit: Faithie/ShutterstockInteractive Proofs for a Language ℒ

ProverClaim/Theorem x
𝑎!
𝑞!
𝑎%
…

accept/reject
Verifier

Def: (𝑃, 𝑉) is an interactive proof for L, if V is probabilistic poly (|x|) time &• Completeness: If x ∈ ℒ, V always accepts.
• Soundness: If x ∉ ℒ, for all cheating prover strategy, V will not accept
except with negligible probability.

23

ZKP MOOC

Interactive Proofs: Notation
Claim/Theorem x
accept𝑎!
/reject𝑞!
𝑎%ProverVerifier…
Def: (𝑃, 𝑉) is an interactive proof for L, if 𝑉 𝑖𝑠 probabilistic poly (|x|) and• Completeness: If x ∈ ℒ, 𝑃𝑟 𝑃, 𝑉 𝑥 = 𝑎𝑐𝑐𝑒𝑝𝑡 = 1.
• Soundness: If x ∉ ℒ, for every 𝑷∗, Pr 𝑃∗, 𝑉 𝑥 = 𝑎𝑐𝑐𝑒𝑝𝑡] = 𝑛𝑒𝑔𝑙( 𝑥 )where negl λ <!

"#$%&#'()$ *for all polynomial functions

24

ZKP MOOC

Interactive Proofs: Notation
Claim/Theorem x
accept𝑎!
/reject𝑞!
𝑎%ProverVerifier…
Def: (𝑃, 𝑉) is an interactive proof for L, if 𝑉 𝑖𝑠 probabilistic poly (|x|) and• Completeness: If x ∈ ℒ, 𝑃𝑟 𝑃, 𝑉 𝑥 = 𝑎𝑐𝑐𝑒𝑝𝑡 = 1.
• Soundness: If x ∉ ℒ, for every 𝑷∗, Pr 𝑃∗, 𝑉 𝑥 = 𝑎𝑐𝑐𝑒𝑝𝑡] = 𝑛𝑒𝑔𝑙( 𝑥 )where negl λ <This is what a proof
for all polynomial functions
ultimatelyis!
!

"#$%&#'()$ *25

ZKP MOOC

Interactive Proofs for a Language ℒ: Notation

ProverClaim/Theorem x
𝑎!
𝑞!
𝑎%
…

accept/reject
Verifier

Def: (𝑃, 𝑉) is an interactive proof for L, if 𝑉 𝑖𝑠 probabilistic poly (|x|) and• Completeness: If x ∈ ℒ, Pr P, 𝑉 𝑥 = 𝑎𝑐𝑐𝑒𝑝𝑡 ≥ 𝑐• Soundness: If x ∉ ℒ, for every 𝑷∗ , Pr 𝑃∗, 𝑉 𝑥 = 𝑎𝑐𝑐𝑒𝑝𝑡 ≤ 𝑠
Equivalent as long as 𝒄 − 𝐬 ≥ 1/poly(|𝑥|)26

ZKP MOOC

The class of Interactive Proofs (IP)ProverClaim/Theorem x
𝑎!
𝑞!
𝑎%
…

accept/reject
Verifier

Def: class of languages IP ={L for which there is an interactive proof}27

ZKP MOOC

What is zero-knowledge?
for every verifier

For true Statements,
What the verifier can computeafter the interaction =What the verifier could have computed
before interaction
How do we capture this mathematically?
28

ZKP MOOC

The Verifier’s View

Prover P

Theorem: T
𝑎!
𝑞!
𝑎%
…

§ After interactive proof, V “learned”:§ T is true (or x ∈ ℒ)
§ A view of interaction (= transcript+ coins V tossed)

Probabilistic
Polynomial timealgorithm
Verifier V

accept/reject T

Def: viewV 𝑷, 𝑽 𝒙 ={(q1,a1,q2,a2,…,coins of V)} .
(probability distribuNon
over coins of V and P)

29

ZKP MOOC

The Simulation Paradigm
V’s view gives him nothing new, if he could have simulated it its own s.t`simulated view’ and `real-view’ are computationally-Indistinguishable
real
VIEWS

??
SIMULATEDVIEWS

The poly-timeDistinguisher

30

30

v1
p1
v2
Accept/rejectv1
p1
v2
Accept/rejectWhen
Theoremis true

ZKP MOOC

Computational Indistinguishability
If no “distinguisher” can tell apart two different
probability distributions they are “effectively the same”.
sampleProbabilistic
Poly Time (k)Distinguisher D

D1

K-BIT STRINGS

D2

K-BIT STRINGS

For all distinguisher algorithms D, even after receiving a polynomial number ofsamples from Db, Prob[D guesses b] <1/2+negl(k)31
ZKP MOOC

Zero Knowledge: Definition
An Interactive Protocol (P,V) is zero-knowledge for a language
𝐿 if there exists a PPT algorithm Sim (a simulator) such that forevery 𝒙 ∈ 𝑳, the following two probability distributions arepoly-time indistinguishable:
1. 𝑣𝑖𝑒𝑤5 𝑃, 𝑉 [𝑥] = {(q1,a1,q2,a2,…,coins of V)}(over coins of V and P)
2. 𝑆𝑖𝑚(𝑥)Def: (P,V) is a zero-knowledge interactive
protocol if it is complete, sound and zero-knowledge
32

ZKP MOOC

Zero Knowledge: Definition
An Interactive Protocol (P,V) is zero-knowledge for a language
𝐿 if there exists a PPT algorithm Sim (a simulator) such that forevery 𝒙 ∈ 𝑳, the following two probability distributions arepoly-time indistinguishable:
Allow simulator S
Expected
Poly-time

1. 𝑣𝑖𝑒𝑤5 𝑃, 𝑉 [𝑥, 16 ] = {(q1,a1,q2,a2,…,coins of V)}(over coins of V and P)
2. 𝑆𝑖𝑚(𝑥, 16 )Def: (P,V) is a zero-knowledge interactive
protocol if it is complete, sound and zero-knowledge
33

Technicality:
Allows sufficient
Runtime onn small x
𝜆- security parameter

ZKP MOOC

What if V is NOT HONEST
EF
D
D
OL
An Interactive Protocol (P,V) is honest-verifier zero-knowledge for a language 𝐿 if there exists a PPT
simulator Sim such that for every 𝑥 ∈ 𝐿,

𝑣𝑖𝑒𝑤5 𝑃, 𝑉 [𝑥] ≈ 𝑆𝑖𝑚(𝑥, 16 )

A
RE

EF
D
L An Interactive Protocol (P,V) is zero-knowledge for alanguage 𝐿 if for every PPT 𝑽∗ , there exists a poly time
simulator Sim s.t. for every 𝑥 ∈ 𝐿,

𝑣𝑖𝑒𝑤5 𝑃, 𝑉 [𝑥] ≈ 𝑆𝑖𝑚(𝑥, 16 )34

ZKP MOOC

Flavors of Zero Knowledge
𝑆𝑖𝑚(𝑥, 1( )𝑣𝑖𝑒𝑤) 𝑃, 𝑉 [𝑥]
REAL≈

SIMULATED§ Computationally indistinguishable distributions = CZK§ Perfectly identical distributions = PZK§ Statistically close distributions = SZK35

ZKP MOOC

Special Case: Perfect Zero Knowledge
verifier’s view can be exactly efficiently simulated`Simulated views’ = `real views’
𝑣𝑖𝑒𝑤+ 𝑃, 𝑉 [𝑥]=??

𝑆𝑖𝑚(𝑥)

Any Algorithm

36

v1
p1
v2
pk
accept/rejectv1
pkp1
v2
Accept/rejectZKP MOOC

Working through a
Simulationfor QR Protocol

37

ZKP MOOC
Credit: Faithie/ShutterstockRecall the Simulation Paradigm
𝑣𝑖𝑒𝑤5 𝑃, 𝑉 :Transcript = 𝑠, 𝑏, 𝑧 ,Coins = 𝑏

38

38

ZKP MOOC

Recall the Simulation Paradigm
𝑣𝑖𝑒𝑤5 𝑃, 𝑉 :𝑠, 𝑏, 𝑧39𝑠𝑖𝑚 :𝑠, 𝑏, 𝑧39

PPT “simulator” 𝑺𝒊𝒎
𝑁, 𝑦

ZKP MOOC

(Honest Verifier) Perfect Zero Knowledge
Claim: The QR protocol is perfect zero knowledge.
Simulator S works as follows:
1. First pick a random bit b.
2. pick a random 𝑧 ∈ 𝑍*∗ .
3. compute s = 𝑧 % /𝑦 + .
4. output (s, b, z).

𝑣𝑖𝑒𝑤5 𝑃, 𝑉 :𝑠, 𝑏, 𝑧claim: The simulated transcript is identically
distributed as the real transcript40

ZKP MOOC

Perfect Zero Knowledge: for all V*
Claim: The QR protocol is perfect zero knowledge.
Simulator S works as follows:
1. First pick a random bit b.
2. pick a random 𝑧 ∈ 𝑍*∗ .
3. compute s = 𝑧 % /𝑦 + .
4. If V*((N,y),s) = b output s, b, z
if not goto 1 and repeat

𝑣𝑖𝑒𝑤5 𝑃, 𝑉 :𝑠, 𝑏, 𝑧Claim: Expected number of repetitions is two
41

ZKP MOOCZK proof of Knowledge

42

ZKP MOOC
Credit: Faithie/ShutterstockProver seems to have proved more: theorem is correct andthat she “knows” a square root mod N
Consider LR = {x : ∃𝒘 𝒔. 𝒕. 𝑹 𝒙, 𝒘 = 𝒂𝒄𝒄𝒆𝒑𝒕} for poly-time relation R.
Def: (P,V) is a proof of knowledge (POK) for LR if :∃ PPT (knowledge) extractor algorithm E s. t. ∀x in L,
in expected poly-time EP(x) outputs w s.t. R(x,w)=accept.
EP(x) (E may run P repeatedly on the same randomness)possibly asking different questions in every executions
This is called the rewinding technique

43

Extractor E
same msg

ZKP MOOC

Prover seems to have proved more not only that theorem iscorrect, but that she “knows” a square root mod N
Consider LR = {x : ∃𝒘 𝒔. 𝒕. 𝑹 𝒙, 𝒘 = 𝒂𝒄𝒄𝒆𝒑𝒕} for poly-time relation R.
Def: (P,V) is a proof of knowledge (POK) for LR if :∃ PPT (knowledge) extractor algorithm E s. t. ∀x in L,
in expected poly-time EP(x) outputs w s.t. R(x,w)=accept.

[if Prob[(P,V)(x)=accept] > a, then EP(x) runs in expected poly(|x|,1/a) time]

EP(x) (may run P repeatedly on the same randomness)
Possibly asking different questions in every executions
This is called the rewinding technique

44

Extractor E
same msg

ZKP MOOCZKPOK that Prover knows a square root x of y mod N
Input: (y,N)

Extractor
Algorithm
s=r2 mod N

Extractor:
On input (y,N),
1. Run prover & receive s
2. Set verifier message tohead; Store r

head
r

45

ZKP MOOC

The Rewinding Method
Input: (y,N)

Extractor
Algorithm
s=r2 mod N
tailrx mod N

46

Extractor:
On input (y,N)
1. Run prover & receive s
2. Set verifier message tohead; receive and store r
3. Rewind and 2nd time set
verifier message to tailreceive rx
4. Output rx/r=x mod N

ZKP MOOCZK Proof for Graph Isomorphism
1
2

10

8
3

1

2
6

5

7

5

9

6
8

3

10

4
4

9

Recall:G0 is isomorphic to G1
If ∃ isomorphism 𝝅: 𝑵 → [𝑵], ∀𝑖, 𝑗: 𝜋 𝑖 , 𝜋 𝑗

47

7∈ 𝐸! iff𝑖, 𝑗 ∈ 𝐸, .

ZKP MOOCZK Interactive Proof for Graph Isomorphism
I will produce a random graph H for which
1: I can give an isomorphism g0 from G0 to H
OR
2: I can give an isomorphism g1 from G1 to H
Thus, ∃isomorphism s from G0 to G1
Verifier, please randomly choose if I should
demonstrate my ability to do #1 or #2.

POINT IS: If I can do both,there exists an isomorphism from G0 to G1
48

ZKP MOOCREPEAT K
INDEPENDENT TIMES.

Input: (G0,G1)
Graph H

Chooserandom g0
permutationof verticesof G0. Set
H=g0(G0)b

Tosscoin bIf b=0: send g0
If b=1: send g0 s-1 (where s(G0)=G1)

Claims: (1) Statement true
can answer correctly for b= 0 and 1(2) Statement false
probb(catch a mistake)≥1/2
1-1/2k(3) Perfect ZK [Exercise]49

ZKP MOOCZKPOK that Prover knows an isomorphism from G1 to G2

H

Extractor
Algorithm

tail
head
gg01

50

Extractor :1) On input H
set coin=head
Store g02) Rewind and 2nd time
set coin=tailStore g1
3) Output g1-1(g0)

ZKP MOOC

The first application: Identity Theft [FS86]
Alice

Amazon (Bob)password...

I accept you as AliceFor Settings:• Alice = Smart Card.
• Over the Net•Breaking ins at Bob/Amazon are possible
Passwords are no good51

ZKP MOOC

Zero Knowledge: Preventing Identity TheftPROVER

VERIFIER

Smart Card
Hard Theorem: I know a
Square root of y mod N

ATM/Main
Frame

Proof: zero knowledge
proof

To identify itself prover proves a hard theorem.
52

ZKP MOOC

Interesting examples, one
application
But, do all NP Languages
have Zero Knowledge
Interactive Proofs?
53

ZKP MOOC
Credit: Faithie/ShutterstockYes: All of NP is in Zero Knowledge
Theorem[GMW86,Naor]: If one-way functions exist, then every
L in NP has computational zero knowledge interactive proofs
Ideas of the proof:
1. Show that an NP-Complete Problem has a ZK interactive Proof[GMW87] Showed ZK interactive proof for G3-COLOR using bit- commitments⇒For any other L in NP, L <p G3-COLOR (due to NPC reducibility)⇒ Every instance x can be reduced to graph Gx such that§
if x in L then Gx is 3 colorable§
if x not in L then Gx is not 3 colorable
54

54

ZKP MOOC

Can you show Zero Knowledge for all of NP [GMW87]
Theorem[GMW86, Naor]: If one-way functions exist, then every L
in NP has computational ZK interactive proofs

Ideas of the proof:
1.[GMW87] Show that an NP-Complete Problem has a ZK interactive Proof if
bit commitments exist
2.[Naor]One Way functions
bit commitment protocol exist

Commit(m)Decommitmmhidingbinding55

ZKP MOOC

Properties of a Bit Commitment Protocol (Commit, Decommit)
between Sender S and Receiver R
Hiding: ∀ receiver R∗ , after commit stage ∀ b, bʹ ∈ {0,1}, view of sender R*{ViewR*{Sender(b),R∗)(1k)} ≈c {ViewR*(Sender(bʹ),R∗)(1k)}[k=sec. param]

Binding: ∀ sender S*, after commit and decommit stage
Prob[R will accept two different values b and b’] < negl(k)K-security parameter
Ex: Use (semantically) secure probabilistic encryption scheme Enc
Commit(b)= “sender chooses r and sends c=Enc(b;r)”Decommit(c) =“sender sends r and b. Receiver rejects unless c=Enc(b;r)”56

ZKP MOOC

All of NP is in Zero Knowledge
Theorem[GMW86,Naor]: If one-way functions exist, then every
L in NP has computational zero knowledge interactive proofs
Ideas of the proof:
1. Show that an G3-COLOR has a ZK interactive Proof
Theorem :is 3-color

57

ZKP MOOC

Theorem :is G3-COLORABLE

On common input graph G =(V,E) & prover input coloring p: V

{0,1,2}

1. Prover: pick a random permutation s of colors {0,1,2} & color
the graph with coloring f(v):=s(p(v)), and commit to each colorof each vertex v by running Commit(f(v)) protocol
2. Verifier: select a random edge e=(a, b) to send to Prover
3. Prover: Decommit colors f(a) & f(b) of vertices a and b
Decision: Verifier rejects If f(a)) ≠ f(b), otherwise Verifier repeats
steps 1-3 and accepts after k iterations
58

ZKP MOOC

Completeness and Soundness§ Completeness: if G is 3-colorable, then the honest proveruses a proper 3-coloring& the verifier always accept.
§ Soundness: If G is not 3-colroable, then for all P*,
Prob[ Verifier accepts]< (1-1/|E|)k < 1/e|E|
for k = |E|2.
§ Zero Knowledge: Easy to see informally, Messy to proveformally59

ZKP MOOC

Honest Verifier Computational ZK
Simulator S in input G=(V,E) : choose at random in advancea challenge (a,b) of the honest verifier V.
§ Choose random edge (a,b) in G
§ Choose colors fa,fb in {0,1,2} s.t fa≠fb at random and forall other v ≠ a,b set fa= 2. Output simulated-view =(commit-transcript to f(v) for all v , edge =(a, b),
decommit-transcript to colors fa,fb )60

ZKP MOOC

Computational ZK: Simulation for any Verifier V*
Simulator S on input G and verifier V*: For i = 1 to |E|2:§ Choose random edge (a, b) and generate commitments com to colors as inhonest verifier simulation.
§ Run V* on com to obtain challenge (a∗, b∗);if (a∗, b∗) = (a, b), then output simulation as honest verifier case,
If all iterations fail, then output ⊥.
Claim: If Commitment scheme is Hiding & Binding, then∀G,p (a true coloring) : prob[⊥ output]=neg(|E|) and if ⊥ is not output, thensimulated-view ≈creal-view
61

ZKP MOOC

Now, we have as many CZK examples as NP-languages}§ n is the product of 2 primes§ x is a square mod n§ (G0,G1) are isomorphic

Stronger Guarantee: PZK§ Any SAT Boolean Formula has satisfying assignment§ Given encrypted inputs E(x) & program PROG, y=PROG(x)§ Given encrypted inputs E(x) & encrypted program E(PROG), y=PROG(x)62

ZKP MOOC

Applications in practiceand in theory

63

ZKP MOOC
Credit: Faithie/ShutterstockProtocol design applications•Can prove relationships between m1 and m2 never revealing either one, only
commit(m1) and commit(m2).
Examples: m1=m2 , m1≠m2 or more generally v=f(m1, m2) for any poly-time f
Generally: A tool to enforce honest behavior in protocols without revealing any
information. Idea: protocol players sends along with each next-msg, a ZK proof
that next-msg= Protocol(history h, randomness r) on history h & c=commit(r)Possible since L={∃𝑟 𝑠. 𝑡. 𝑛𝑒𝑥𝑡 − 𝑚𝑠𝑔 = 𝑃𝑟𝑜𝑡𝑜𝑐𝑜𝑙 ℎ, 𝑟 𝑎𝑛𝑑 c=commit(r)} in NP.

64

ZKP MOOC

Uses for Zero Knowledge Proofs 90-onwards
Computation Delegation [Kalai, Rothblum x 2, Tromer,…]
Zero Knowledge and Nuclear Disarmament [Barak et al]
Zero Knowledge and Forensics [Naor etal]
Zcash: Bit Coin with privacy and anonymity [BenSasson, Chiesa et al]
Zero Knowledge and Verification Dilemmas in the Law [Bamberger etal]

65

ZKP MOOC

Complexity Theory: Randomized Analogue to NP
Efficiently
SolvableP

Efficiently
Verifiable

NP

BPP(randomized poly time)IP

Q: Is IP greater than NP?
66

ZKP MOOC

Claim: G0 is Not Isomorphic to G1(in co-NP, not known to be in NP)
1
2

G0

10

8

1

2
6

5

7

5

9

3

6
8

3

10

4
9

4

G1

7

Shortest classical proof:»exponential n! for n vertices
But can convince with an efficientinteractive proof
67

67

ZKP MOOC

Graph Non-Isomorphism in IP
input: (G0, G1)

H = g(Gc)
if H isomorphic
to G0 then b = 0,else b = 1

bflip coin c Î{0,1}pick random g
Reject if b ≠ c

Claim: Completeness&Soundness hold68

Accept after n repetitions

ZKP MOOC

Graph Non-Isomorphism in IP
input: (G0, G1)
H = g(Gc)
if H isomorphic to
G0 then b = 0,else b = 1

bflip coin c Î{0,1} pickrandom g
Reject if b ≠ c
Accept otherwise

Not ZK! V* can learn if graph H of its choice is isomorphic to G0 or G1.
Idea for fix: V proves to P in ZK that he knows an isomorphism g
69

ZKP MOOC

Arthur-Merlin Games [BaM85]
Merlin“x in L”

ArthurCoin Tosser+
Decision Function
Accepts or Rejects x

coins
coins

GNI requires verifier to keep its coins secret as in IP protocols
Is coin privacy necessary?

Theorem[GoldwasserSipser86]: AM (protocols with Public Coins) = IP
Idea: Merlin proves to Arthur “the set of private coin executions that would
make Verifer accept” is large. Technique= prove lower bound on size of sets70

ZKP MOOC

AM Protocols enable “in practice” removal ofinteraction: the Fiat-Shamir Paradigm[FS87]§ Let H:{0,1}*{0,1}k be a cryptographic Hash function
a1
Coins
a2

§ Can take an AM protocol§ Replace by
Fiat-Shamir Heuristic:
If H is random-oracle,thencompleteness&soundness hold,
Use H –hash function(a1, H(a1), a2)

71

Coin Tosser+
Decision Function
V(input x, a1,coins,a2)=Accept or Rejects

V(x, a1,H(x,a1), a2)=Accept or Rejects
ZKP MOOC

AM Protocols suggest “in practice” removal ofinteraction: the Fiat-Shamir Paradigm[FS87]§ LetthisH:{0,1}*{0,1}every
be ainteractive
cryptographic
functionto AM
Warning:
does NOT mean
ZK proofHash
can transform
protocols and then use Fiat-Shamir heuristic,
Since IP =AM transformation requires extra super-polynomial
powersCoin
fromTosser+
Merlin
a1
§
Can
take
an
AM
protocolAnd for Fiat-Shamir heuristic to work, Prover must beCoinscomputationallyDecisionboundedso
Function
not to be able to invert H
a2
V(input x, a1,coins,a2)
Yet, §many
specific
protocols,canbenefitfromthisheuristic
Replace by=Accept or RejectskFiat-Shamir Heuristic:
If H is random-oracle,thencompleteness&soundness hold(a1, H(a1), a2)

72

V(x, a1,H(x,a1), a2)=Accept or Rejects
ZKP MOOC

AM Protocols suggest “in practice” removal ofinteraction: the Fiat-Shamir Paradigm[FS87]§ Let H:{0,1}*{0,1}k be a cryptographic Hash function§ Can take an AM protocol
Q: What if first message are coins from Arthur?

§ Replace by

Coins
a1
Coins
a2

Coin Tosser+
Decision Function
V(x, a1,coins, a2)=Accept
or Rejects

Idea(used later in course extensively):
Fiat-Shamir Heuristic:
Post first message coins as a “publicly” chosen randomness for all to see
If H is random-oracle,then(a1, H(x, a1), a2)proofs
V(x, a1,H(a1), a2)=Accept
and then apply Fiat-Shamir heuristics to get non-interactive
completeness&soundness holdor Rejects
73

ZKP MOOC

IP: Complexity Theory Catalyst
Decoupled “Correctness” from “Knowledge of the proof”
Ask new questions about nature of proof
Questions have been asked and answered inlast 30+ years leading up to current research on
Provably outsourcing computation

74

ZKP MOOC

Classically: Can Efficiently VerifyNP∃solution

Co-NP

0 solutions?
#P?
PSPACE ?

2100 -13 solutions∀∃∀…∃

Can you prove more via interactive proofs?
75

ZKP MOOC

Interactively Provable= PSPACE[FortnowKarloffLundNissan89,
Shamir89]

NP
q1
a1
q2

Co-NP
#P
PSPACE=IP

Accept/RejectOther Ways to define probabilistic proof systems?
76

ZKP MOOC

The Arrival of the Second Prover (MIP)[BenorGoldwasserKilianWigderson88]

NP

Unconditionally: NP =PZK
P1

Co-NP
#P
PSPACE

Claim TV

P2

Accept/RejectCould two prove more than one?
Intuition: Can check consistency,
Verifier catches provers if deviate
77

ZKP MOOC

The Second Prover is a Game Changer (MIP)
NP

P1

Co-NP

P2

#P
PSPACENEXPTIME[BabaiFortnowLund90]

Claim T
V

Accept/Reject

PCP theorem [FGLSS, AS, ALMSS91]:

NP statements can be verified with highprob. by only reading a constant number ofbits of the proof→NP-Hardness of Approximation Problems
78

ZKP MOOC

Impact on Quantum Computing
Q: Can the correctnessof a Quantum
polynomial
time computation
be checked by aclassical verifier?

Quantum Polynomial time
Classical Verifier

Accept/reject

Theorem[ReichardtUngerVazirani13]:
A classical Verifier can verify the computation of two entangled
but non-communicating poly-time quantum algorithms
79

ZKP MOOC

Quantum MIP is All Powerful
P1

Classical Verifier

P2

2020:

Accept/reject

MIP* = Recursively Enumerable Languages[Ji, Natarajan,Vidick, Wright, Yuen]

80

ZKP MOOCAside:The Resistance81

ZKP MOOC
Credit: Faithie/Shutterstock1983–1985 (The Resistance)82

1983–1985 (The Resistance)83

1983–1985 (The Resistance)
Let me show you how to do it!

84

1985 (The Acceptance)
We are very happy to inform you that your paper“The Knowledge Complexity of Interactive Proof Systems”
has been selected for presentation at the 17th Symposium on Theory ofComputing85

Broader Lessons§ Pay attention to good ideas§ It may take a long time >30 years togo from the basic idea to impact