Guest Lecturer: Alex Lombardi
Instructors: Dan Boneh, Shafi Goldwasser, Dawn Song, Justin Thaler, Yupeng Zhang Authentication Blockchains and cryptocurrencies secure multiparty computation ZKP MOOC 2 What does theoretical research on proof systems look like?
Feasibility (do they exist in principle?) . SNAR(G/K)s, other protocols (ZK, WI, WH, etc.) . Strong attack models (Concurrent? Quantum?)
ZKP MOOC
4
Feasibility (do they exist in principle?) . SNAR(G/K)s, other protocols (ZK, WI, WH, etc.) ■ Strong attack models (Concurrent? Quantum?) Minimize Assumptions (to the extent possible) ■ Trusted setup (CRS/URS/plain model) ■ Security reduction based on simple, well-studied, falsifiable assumptions.
ZKP IMOOG
5

Feasibility (do they exist in principle?)
. SNAR(G/K)s, other protocols (ZK, WI, WH, etc.) . Strong attack models (Concurrent? Quantum?)
Minimize Assumptions (to the extent possible)
■ Trusted setup (CRS/URS/plain model) . Security reduction based on simple, well-studied, falsifiable assumptions.
Improve efficiency
. . Amount of communication, number of rounds Prover/verifier efficiency
ZKP IMOOG
6

Feasibility (do they exist in principle?) . SNAR(G/K)s, other protocols (ZK, WI, WH, etc.) ■ Strong attack models (Concurrent? Quantum?) +Applications
Minimize Assumptions (to the extent possible)
■ Trusted setup (CRS/URS/plain model) . Security reduction based on simple, well-studied, falsifiable assumptions.
Improve efficiency
. . Amount of communication, number of rounds Prover/verifier efficiency
ZKP IMOOG
7
. No trusted setup allowed. . Security against Malicious verifier hard to guarantee.
ZKP MOOC
99

. No trusted setup allowed. . Security against Malicious verifier hard to guarantee. . Lecture 1: ZK for NP [GMW86] with inverse poly soundness error. How do we reduce the error?
ZKP MOOC
10

. No trusted setup allowed. . Security against Malicious verifier hard to guarantee. . Lecture 1: ZK for NP [GMW86] with inverse poly soundness error. How do we reduce the error? "    Sequential repetition works (but very inefficient). . Parallel repetition reduces soundness error but *may not* preserve ZK! Let’s see why:
ZKP MOOC
11

Claim: This graph has a 3-coloring. V ZKP MOOC 12
0 11 2 V 13
V 2) Commit 14
V 2) Commit 0 1 2 (d, f ) 1) Sample a challenge edge. ZKP MOOC 15
V 2) Commit (d, f ) 1) Sample a challenge edge. 1 2 2) Accept if colors are different. 3) Reveal edge colors ZKP MOOC 16
J /* ZK Simulator: guess Verifier's challenge in advance, and rewind if the guess was wrong. 1) Guess (x,y) 2) Pick two random bits 3) Commit (x',y') If (x,y) ≠ (x',y') ZKP MOOC 17
P V If there are t repetitions, over 2 t possible challenges to guess from! Would take exponential time.
P V In fact, it turns out that this protocol really shouldn't be ZK! [DNRS99]: If you can do Fiat-Shamir for Π, then Π wasn't malicious-verifier ZK.
. No trusted setup allowed. . . Security against Malicious verifier hard to guarantee. Many lines of research devoted to understanding the feasibility of interactive ZK.
ZKP MOOC
20

. No trusted setup allowed. . . Security against Malicious verifier hard to guarantee. Many lines of research devoted to understanding the feasibility of interactive ZK. "    How many communication rounds? [BKP18] suggests that you can do it in 3. ▪ How efficient can you make the prover? [IKOS07, ...] "    Stronger forms of security: quantum attacks, concurrency
ZKP MOOC
21
Main Topics:
x, crs P(w)
V •   Completeness: if x ∈ L, V accepts honest P with probability 1 — negl •   Computational Soundness: if x  £ L, for all efficient P*, V rejects w.p. 1 — negl • Succinctness: proof has length poly(λ, log(|x| + |w|)) and verification is fast. 23
x, crs P(w)
V •   Completeness: if x ∈ L, V accepts honest P with probability 1 — negl •   Computational Soundness: if x  £ L, for all efficient P*, V rejects w.p. 1 — negl • Succinctness: proof has length poly(λ, log(|x| + |w|)) and verification is fast. This class so far: constructions of SNARGs using IOPs and a random oracle.
Powerful, general proposal for removing interaction. Interactive Non-Interactive P β = h(α) If h is modeled as a random oracle, securely compiles any constant-round public coin protocol. ZKP MOOC 25
What does that mean? If h is modeled as a random oracle, securely compiles any constant-round public coin protocol. ZKP MOOC 26
Assumption about the structure of an attack on a hash function h : “The best you can do is treat h as a black box in your attack.” Under such an assumption, h( · ) can be thought of as a random function. ZKP MOOC
27

Claim: Fiat-Shamir for constant-round protocols is secure in the ROM Proof (3 message case): α must come from one of the oracle queries
ZKP MOOC
28

Claim: Fiat-Shamir for constant-round protocols is secure in the ROM Proof (3 message case): V α must come from one of the oracle queries
ZKP MOOC
29

Claim: Fiat-Shamir for constant-round protocols is secure in the ROM Proof (3 message case): V α must come from one of the oracle queries 1/Q security loss
ZKP MOOC
30

Assumption about the structure of an attack on a hash function h : “The best you can do is treat h as a black box in your attack.” Under such an assumption, h( · ) can be thought of as a random function. ZKP MOOC
31

Assumption about the structure of an attack on a hash function h : “The best you can do is treat h as a black box in your attack.” In practice, h( · ) is instantiated with (e.g.) SHA256, possibly salted.
ZKP MOOC
32

Assumption about the structure of an attack on a hash function h : “The best you can do is treat h as a black box in your attack.” No matter what, h(·) is instantiated with a public efficient algorithm.
ZKP MOOC
33
Obvious (theoretical) problem: Public efficient algorithms can't compute random functions Next: example of an uninstantiable random oracle property [CGH98]
Fix a function f : {0,1}* → {0,1}^ We say that a hash function h is Correlation Intractable (CI) for f if it is hard to find x such that h(x) = f (x) A PPT A, r, [h(x) = f(x)] = negl X{A(h)
36

For any fixed f , a RO is CI for f . Why? Each query x to the RO produces a random output y, which is equal to f (x) with probability 2-x.
ZKP MOOC
37

Claim [CGH98]:ﾖƒ such that for any (efficient) hash family H , H fails to be CI for f !
ZKP MOOC
38

Claim [CGH98]:ﾖƒ such that for any (efficient) hash family H , H fails to be CI for f ! f (x):  interpret x as a program P and output P (x).
ZKP MOOC
39

Claim [CGH98]:ﾖƒ such that for any (efficient) hash family H , H fails to be CI for f ! f (x):  interpret x as a program P and output P (x). Given h ← H , attack sets x = 〈h〉to be a description of h . Then, f (x) = P(x) = P((h)) = h((h)) = h(x).
40

Is this a reasonable counterexample? ▪ Hash function/random oracle must be able to hash inputs of arbitrary length. CI with bounded inputs might exist!
ZKP MOOC
41

Is this a reasonable counterexample?
▪ Hash function/random oracle must be able to hash inputs of arbitrary length. CI with bounded inputs might exist! ▪ [Barak01,GK03] apply to fixed-input length hash functions.
ZKP MOOC
42

Is this a reasonable counterexample? ▪ Hash function/random oracle must be able to hash inputs of arbitrary length. CI with bounded inputs might exist! ▪   [Barak01,GK03] apply to fixed-input length hash functions. Theorem [Barak ‘01, Goldwasser-Kalai ‘03]:ﾖinteractive protocol Π such that Π FS is ROM-secure but insecure for any efficiently computable H (e.g. SHA-3).
ZKP MOOC
43

Is this a reasonable counterexample? ▪ Hash function/random oracle must be able to hash inputs of arbitrary length. CI with bounded inputs might exist! ▪ [Barak01,GK03] apply to fixed-input length hash functions. ▪ Security property broken by running the hash function on its own description. Is this practically relevant?
ZKP MOOC
44

Is this a reasonable counterexample?
▪ Hash function/random oracle must be able to hash inputs of arbitrary length. CI with bounded inputs might exist! ▪   [Barak01,GK03] apply to fixed-input length hash functions. ▪ Security property broken by running the hash function on its own description. Is this practically relevant? ▪ Recursive SNARKs do something of this flavor.
ZKPIMOOC
45

Is this a reasonable counterexample?
▪ Hash function/random oracle must be able to hash inputs of arbitrary length. CI with bounded inputs might exist! ▪   [Barak01,GK03] apply to fixed-input length hash functions. ▪ Does NOT imply RO-based SNARKs are broken in practice. . But it does imply a lack of theoretical understanding.
ZKP MOOC
46
What can we do without random oracles?
Prove security assuming that some concrete algorithmic task is infeasible: ▪ Computing discrete logarithms is hard. ▪ Solving random noisy linear equations (LWE) is hard. ▪ SHA256 is collision-resistant.
ZKP MOOC
48

Many cryptographic constructions use random oracles to get better efficiency, but can be based on falsifiable assumptions. ▪ CCA-secure public key encryption. ▪ Identity-based encryption. ▪ Non-interactive zero knowledge.
ZKP MOOC
49

Can (ZK-)SNARKs for NP be built based on falsifiable assumptions? ▪ (minor caveats but) No! ▪  No way to extract a long witness from a short proof. Need assumption (RO, “knowledge assumption”) that guarantees adversary “knows” a long string given a short commitment.
ZKP MOOC
50

Can (ZK-)SNARGs for NP be built based on falsifiable assumptions? ▪ It's complicated. (We don't know) ▪ Significant barriers [Gentry-Wichs ‘11] ▪ The community is still trying to understand this.
ZKP MOOC
51
Rest of today: SNARGs for limited computations from falsifiable assumptions (LWE) Creating Equipe/Stations in th
▪ Correlation-intractable hash functions [cchlrrw19,ps19,hlr21] ▪  Used to instantiate Fiat-Shamir without random oracles, for “nice enough” interactive protocols. ▪  Somewhere extractable commitments [HW15] ▪ Used to make a “nice enough” interactive protocol ▪ Special variant of the typical IOP-based approach.
ZKPIMOOC
53

A hash family H is Cl for f if ∀ PPT A, Pr, [h(x) = f(x)] = negl X{A(h) ZKP MOOC
54

A hash family H is Cl for binary relation R if ∀ PPT A, [(x, h(x)) ∈ R] = negl X{A(h)
ZKP MOOC
55

A hash family H is Cl for f if ∀ PPT A, [h(x) = f(x)] = negl X{A(h) ▪ Weren't these impossible to build? ▪ Restrict to fixed input length (necessary) ▪ Restrict to fixed running time on f (unclear if necessary)
56

Here's a simple construction [CLW18] using Fully Homomorphic Encryption (FHE)
ZKP MOOC
57
Real hash key: g ≡ 0 (or a uniform random string – nobody can tell)
Key point: g is hidden to everyone! We consider different g to prove security. ZKP MOOC
58

Suppose an attacker, given (h), finds x such that h(x) = f (x). Key idea: let g*(x) = Dec(f(x)) + 1. We know that Enc(g) ≈ Enc(g*) if the encryption scheme is (circular-)secure.
Dec(f(x)) = Dec(h(x)) = g*(x) = Dec(f(x)) + 1. Impossible!
ZKP MOOC
59

[(x,h(x)) ∈ R] = negl . Constructions for efficiently computable functions: ▪ From LWE ([CLW18,PS19,LV22]) . From DDH (JJ21) . Construction [HLR21] for (efficient) relations with “product structure”
60
How do we use CI to instantiate Fiat-Shamir?
V Def: Given false claim x and a first message α , a challenge β is “bad” if there exists a prover message γ making V accept. We want to say: if the (3 message) interactive protocol is sound, then (for all x, α) most β are not bad. True for statistically sound IPs. P
ZKP MOOC
62

V Exactly what Cl is good for! Define relation R x =  {(α,β):β is bad}. Then if h is Cl for R x (when x  # L), Π fs is sound using h! Protocols with more than 3 messages: round-by-round soundness (each round has a type of “bad challenge” to avoid).
ZKP MOOC
63

V Main challenges: Sometimes our IP doesn't have statistical soundness. 1) We can only build CI for relations R that can be decided efficiently. 2)
ZKP MOOC
Important example: SNARGs via IOPs (PCPs)
P(x,w) Compute (long) proof string π from ( x, w ) Com(π) r (describes location set S) Open πς V(x) r ← {0,1}λ Verify opening, check consistency of πς Candidate SNARG: apply Fiat-Shamir to this protocol! Simplified (less efficient) version of modern SNARKs you've learned about. ZKP MOOC
66

P(x,w) Compute (long) proof string π from ( x, w ) Com(π) r (describes location set S) Open πς V(x) r ← {0,1}λ Verify opening, check consistency of πς Not statistically sound, so it's not clear how to analyze FS without random oracles. ZKP MOOC
67

TT • Completeness: if x į ∈ L for all i, V accepts honest P • Computational Soundness: if x i  £ L for some i, for all efficient P*, V rejects. • Succinctness: proof has length poly(λ, |w|, log k) Surprisingly powerful (implies SNARGs for P, etc.)
ZKP MOOC
68

P(x 1, …, x k, W 1, …, W k, Com(π1, …, πκ) r (describes location set S) Open π 1,5, … π k,5
r ← {0,1}λ Verify opening, check consistency of πς ZKP MOOC
69

Com(π 1 , … , π κ ) r (describes location set S) Open π 1,5, … π k,5
Verify opening, check consistency of πς Choose Com to be statistically binding on one out of k proofs (π 1 ) If x i is false, protocol is now statistically sound! (π 1 is fixed) ZKPIMOOC
70

ZKP MOOC 71
ZKP MOOC 72
ZKP MOOC
73

Com(π 1 , … , π κ ) r (describes location set S) Open π 1,5, … π k,5
Verify opening, check consistency of πς Choose Com to be statistically binding on one out of k proofs (π 1 ) If x i is false, protocol is now statistically sound! (π 1 is fixed) ZKPIMOOC
74

Com(π1,…,πκ) r (describes location set S) Open π 1,5, … π k,5
Verify opening, check consistency of πς Choose Com to be statistically binding on one out of k proofs (π k ) If x i is false, protocol is now statistically sound! (π k is fixed) ZKPIMOOC
75

Com(π 1 , … , π k ) r (describes location set S) Open π 1,5, … π k,5
Verify opening, check consistency of πς With some work, can use CI hash functions to compile this protocol. Succinctness: |w| · λ + k · λ, but can be reduced to |w| · λ by recursing. ZKP MOOC
76

. Use hash functions that are CI for appropriate functions/relations ▪　[CCHLRRW19,PS19,BKM20,JJ21,HLR21] . Carefully show that FS-soundness for protocols of interest follows from compatible forms of Cl ▪ [CCHLRRW19]: (non-succinct) NIZK ▪ [JKKZ21]: non-interactive sumcheck protocol ▪ [CJJ21]: batch NP arguments
ZKP MOOC
77

Open problems: . Characterize which protocols can be FS-compiled (we know it doesn't work in general [Bar01, GK03]) . SNARGs for NP from falsifiable assumptions?
ZKP MOOC
78