Zero-Knowledge Proofs in Cryptography
Exploring zero-knowledge proofs in cryptography, this content delves into interactive protocols, perfect zero-knowledge definitions, and the QR protocol's honest verifier and malicious verifier zero-knowledge theorems. It discusses how simulators work to maintain zero-knowledge properties and the significance of multiple random proofs to convince verifiers without revealing sensitive information.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
MIT 6.875 Foundations of Cryptography Lecture 14
ZK Definition An Interactive Protocol (P,V) is perfect zero-knowledge for a language ? if for every PPT ? , there exists a (expected) poly time simulator S s.t. for every ? ?, the following two distributions are identical: 1. ????? (?,? ) 2. ?(?,1?) Analogously: statistical and computational zero-knowledge
Zero Knowledge Interactive Proof for QR = { ?,? :? is a quadratic residue mod ?}. ? = ?2 (mod ?) ?,? ?,? ? {0,1} If b=0: ? = ? Check: ?2= ??? (mod ?) If b=1: ? = ??
We Proved: Thm: The QR protocol is honest verifier zero knowledge. Simulator S works as follows: 1. First pick a random bit b. . 2. pick a random ? ?? 3. compute s = ?2/??. ??????,? : ?,?,? 4. output (s,b,z). Claim: The simulated transcript is identically distributed as the real transcript in the interaction (P,V).
NOW: (Malicious Ver) Zero Knowledge Theorem: The QR protocol is (malicious verifier) zero knowledge. Simulator S works as follows: 1. First pick a random s and feed it to ? . 2. Let b = ? (?). Now what??? ????? ?,? : ?,?,?
(Malicious Ver) Zero Knowledge Theorem: The QR protocol is (malicious verifier) zero knowledge. Simulator S works as follows: ?2 ?? for a random z and feed s to ? . 2. Let b = ? (?). 1. First set ? = 3. If ? = ?, output (s,b,z) and stop. 4. Otherwise, go back to step 1 and repeat. (also called rewinding ).
Simulator S works as follows: ?2 ?? for a random z and feed s to ? . 2. Let b = ? (?). 1. First set ? = 3. If ? = ?, output (s,b,z) and stop. 4. Otherwise, go back to step 1 and repeat. (also called rewinding ). Lemma: (1) S runs in expected polynomial-time. (2) When S outputs a view, it is identical to the view of ? in a real execution.
What Made it Possible? 1. Each statement had multiple proofs of which the prover chooses one at random. 2. Each such proof is made of two parts: seeing either one on its own gives the verifier no knowledge; seeing both imply 100% correctness. 3. Verifier chooses to see either part, at random. The prover s ability to provide either part on demand convinces the verifier.
ZK Proof for Graph Isomorphism 1 1 2 6 6 2 5 7 10 8 3 5 9 8 10 4 3 4 7 9 Graph G Graph H ? = ?(?) ? = ?(?) where ? is a random permutation random challenge bit ? Verifier Prover ? = 0: send ?0 s.t. K = ?0(?) ? = 1: send ?1 s.t. H = ?1(?)
ZK Proof for Graph Isomorphism Completeness: Exercise. ? = ?(?) ? = ?(?) where ? is a random permutation random challenge bit ? Verifier Prover ? = 0: send ?0= ? ? = 1: send ?1= ? ? 1
ZK Proof for Graph Isomorphism Soundness: Suppose G and H are non-isomorphic, and a prover could answer both the verifier challenges. Then, K = ?0(?) and H = ?1? . In other words, H = ?1 ?0(?), a contradiction! ? = ?(?) ? = ?(?) where ? is a random permutation random challenge bit ? Verifier Prover ? = 0: send ?0= ? ? = 1: send ?1= ? ? 1
ZK Proof for Graph Isomorphism Zero Knowledge: Exercise. ? = ?(?) ? = ?(?) where ? is a random permutation random challenge bit ? Verifier Prover ? = 0: send ?0= ? ? = 1: send ?1= ? ? 1
Efficient Prover (given a Witness) In both these protocols, the (honest) prover is actually polynomial-time given the NP witness (the square root of ? in the case of QR, and the isomorphism in the case of graph-iso.) Soundness is nevertheless against any, even computationally unbounded, prover ? .
Do all NP languages have Perfect ZK proofs? We showed two languages with perfect ZK proofs. Can we show this for all NP languages? Theorem[Fortnow 89, Aiello-Hastad 87] No, unless bizarre stuff happens in complexity theory (technically: the polynomial hierarchy collapses.)
Do all NP languages have ZK proofs? Nevertheless, today, we will show: Theorem [Goldreich-Micali-Wigderson 87] Assuming one-way permutations exist, all of NP has computational zero-knowledge proofs. The assumption can be relaxed to one-way functions. This theorem is amazing: it tells us that everything that can be proved (in the sense of Euclid) can be proved in zero knowledge!
Zero Knowledge Proof for 3-Coloring NP-Complete Problem: Every other problem in NP can be reduced to it. Let us first design a protocol in the lead-box model.
Let us first design a protocol in the lead-box model. Bit b Commit to b: b b Receiver Sender Open: b, 1. Hiding: The lead-box should completely hide b. 2. Binding: Sender shouldn t be able to open to 1-b.
We will later show how to implement such a lead-box (as a commitment protocol) using one-way permutations. Bit b ACCEPT/ REJECT Commit to b: b Receiver Sender Open: b, 1. Hiding: The lead-box should completely hide b. 2. Binding: Sender shouldn t be able to open to 1-b.
Zero Knowledge Proof for 3COL 1 2 2 1 Graph G =(V,E) Graph G 3 3 4 4 (? 1 , ,?(?)) random edge (?,?) Come up with a random permutation of the colors ?:? {?,?,?} open (?) and (?) 1. Check the openings 2. Check: ? , ? {?,?,?} 3. Check: ? ? .
Zero Knowledge Proof for 3COL 1 2 2 1 Graph G =(V,E) Graph G 3 3 4 4 (? 1 , ,?(?)) random edge (?,?) open (?) and (?) Completeness: Exercise.
Zero Knowledge Proof for 3COL 1 2 2 1 Graph G =(V,E) Graph G 3 3 4 4 (? 1 , ,?(?)) random edge (?,?) open (?) and (?) Soundness: If the graph is not 3COL, in every 3-coloring (that P commits to), there is some edge whose end-points have the same color. V will catch this edge and reject with probability 1/|?|.
Zero Knowledge Proof for 3COL 1 2 2 1 Graph G =(V,E) Graph G 3 3 4 4 (? 1 , ,?(?)) random edge (?,?) open (?) and (?) Repeat |?| ? times to get the verifier to accept with probability (1 1/|?|)|?| ? 2 ?
Commitment Schemes ACCEPT/ REJECT Commitment Protocol ???,??? (? ?,1?,? 1?) Bit b Receiver R COM Sender S DEC b, DEC 1. Completeness: R always accepts in an honest execution.
Commitment Schemes ACCEPT/ REJECT Commitment Protocol ???,??? (? ?,1?,? 1?) Bit b Receiver R COM Sender S DEC b, DEC 2. Computational Hiding: For every possibly malicious (PPT) ? , ????? (? 0 ,? ) ?????? (? 1 ,? )
Commitment Schemes ACCEPT/ REJECT Commitment Protocol ???,??? (? ?,1?,? 1?) Bit b Receiver R COM Sender S DEC b, DEC 3. Perfect Binding: For every possibly malicious ? , let com be the receiver s output in an execution of ? ,? . There is no pair of decommitments ???0,???1 s.t. R accepts both com,0,???0 and (com,1,???1).
A Commitment Scheme from any OWP Bit b ??? = (? ? ,???(?) ?) Receiver R Sender S ??? = ? Let ??? = ?,? . Check that 1. ? ? = ? and 2. ???(?) ? = y ????:(?,?) 1. Completeness: Exercise. 2. Comp. Hiding: by the hardcore bit property. 3. Perfect Binding: because f is a permutation.
Back to ZK Proof for 3COL 2 2 1 1 Graph G =(V,E) Graph G 3 3 4 4 ? {??? ? ? ;??}?=1 random edge (?,?) send openings ?? and ??
Why is this zero-knowledge? Simulator S works as follows: 1. First pick a random edge (? ,? ) Color this edge with random, different colors Color all other edges red. ? {??? ? ? ;??}?=1 edge (?,?) 2. Feed the commitments of the colors to ? and get edge (?,?) 3. If ?,? (? ,? ), go back and repeat. send openings ?? and ?? 4. If ?,? = (? ,? ), output the commitments and openings ?? and ?? as the simulated transcript.
Why is this zero-knowledge? ? {??? ? ? ;??}?=1 Lemma: (1) Assuming the commitment is hiding, S runs in expected polynomial-time. (2) When S outputs a view, it is identical to the view of ? in a real execution. edge (?,?) send openings ?? and ??
Examples of NP Assertions My public key is well-formed (e.g. in RSA, the public key is ?, a product of two primes together with an e that is relatively prime to ? ? .) Encrypted bitcoin (or Zcash): I have enough money to pay you. (e.g. I will publish an encryption of my bank account and prove to you that my balance is $?.) Running programs on encrypted inputs: Given Enc(x) and y, prove that y = PROG(x).
Examples of NP Assertions Running programs on encrypted inputs: Given Enc(x) and y, prove that y = PROG(x). More generally: A tool to enforce honest behavior without revealing information.
Interaction is Necessary for ZK Suppose there were an non-interactive ZK proof system for 3COL. Graph G Graph G ? Step 1. When G is in 3COL, V accepts the proof ?. (Completeness)
Interaction is Necessary for ZK Suppose there were an non-interactive ZK proof system for 3COL. Graph G Graph G ? Step 2. PPT Simulator S, given only G in 3COL, produces an indistinguishable proof ?(Zero Knowledge). In particular, V accepts ?.
Interaction is Necessary for ZK Suppose there were an non-interactive ZK proof system for 3COL. Graph G Graph G ? Step 3. Imagine running the Simulator S on a ? 3COL. It produces a proof ?which the verifier still accepts! (WHY?! Because S and V are PPT. They together cannot tell if the input graph is HAM or not)
Interaction is Necessary for ZK Suppose there were an non-interactive ZK proof system for 3COL. Graph G Graph G ? Step 4. Therefore, S is a cheating prover! Produces a proof for a ? 3COL that the verifier nevertheless accepts. Ergo, the proof system is NOT SOUND!
