Report

Sigma Protocols and (Non-Interactive) Zero Knowledge Rennes, 24/10/2014 CIDRE/ INRIA Cristina Onete What is zero-knowledge? Zero-knowledge proof: “a method by which one party […] can prove to another party […] that a […] statement is true, without conveying any [further] information” Wikipedia, en.wikipedia.org Preuve à divulgation nulle de connaissance: “un protocole […] dans lequel une entité […] prouve […] à une autre entité […] qu’une proposition est vraie sans […] révéler une autre information.” Wikipedia, fr.wikipedia.org Cristina Onete || 24/10/2014 || 2 So far chg resp Prover Verifier No anonymity: • = ℎ or = (ℎ) Anonymity in a ring: = (ℎ) Anonymity and traceability: = (ℎ) Now: Deniability/Zero-Knowledge! Cristina Onete || 24/10/2014 || 3 Sigma ( ) protocols Setup: we have a secret witness and a public statement and a function : × → {0,1} Idea: Prover must prove she has such that , = 1 without revealing anything else Example 1: finite fields Group =< > with p prime, : 1, … , − 1 × = {0,1} , = 1 iff. = protocol Prover = ; = Verifier I know the discrete log of = Cristina Onete || 24/10/2014 || 4 Sigma ( ) protocols Setup: witness , statement , function : × → {0,1} Idea: Prover proves she has s.t. , = 1, but no more Example 2: RSA Modulus = , order = ( − 1)( − 1), co-prime with : ∗ × ∗ → 0,1 ; , = 1 iff. = ( ) protocol Prover = ; = Verifier , = I know the message encrypted in Cristina Onete || 24/10/2014 || 5 Sigma ( ) protocols Setup: witness , statement , function : × → {0,1} Idea: Prover proves she has s.t. , = 1, but no more Example 3: Composition Group =< > with p prime, : ∗ × = {0,1} , = {1 , … , } = 1 iff. ∃ ∈ 1, … , . . = protocol Prover = ; = Verifier = {1 , … , } I have the corresponding to one of ′ Cristina Onete || 24/10/2014 || 6 Contents Commitment Schemes Sigma Protocols • Structure • Properties • Schnorr’s protocol Composition of Sigma Protocols • Parallel composition • AND composition • EQ and OR compositions The Fiat-Shamir heuristic Commitment Schemes Bob Alice Alice Bob Example: • • Alice and Bob must agree who will clean tonight They are at their offices. Each tosses a coin & they call: If tosses are the same, then Alice cleans If tosses are different, then Bob cleans • Who talks first? Cristina Onete || 24/10/2014 || 8 Commitment Schemes Alice Bob Alice Bob Alice and Bob toss • Alice talks first Bob says he tossed the same value • Bob talks first Alice says she tossed the opposite value How can we avoid this? Cristina Onete || 24/10/2014 || 9 Commitment Schemes Bob cleans Alice Bob Commitment: an envelope with a strange seal • Alice talks first • Commit phase: she hides toss in envelope, gives it to Bob • Bob reveals toss • Reveal phase: Alice tells Bob how to unseal envelope Cristina Onete || 24/10/2014 || 10 Commitment Schemes Alice Bob Properties: • Hiding: The content of the envelope is not visible Bob doesn’t know anything about Alice’s toss • Binding: Alice can’t change the content in the envelope Alice can’t cheat after getting Bob’s toss Cristina Onete || 24/10/2014 || 11 Commitment Schemes = (, ) Input …………………… Random , Alice Bob Check = (, ) Formally: : {0,1} × {0,1}∗ → {0,1}∗ Commitment hiding: Dist 1 , ≈ Dist ((2 , )) Commitment binding: ∀ 1 , 2 ∈ 0,1 ∗ : Prob , ′ ← : 1 , = 2 , ′ Cristina Onete || 24/10/2014 ≪1 || 12 Pedersen Commitments = (, ) ∈ {0,1} …………………… Random , Alice Bob Check = (, ) Setup: ∗ = < >, prime field, ℎ = ∈ ∗ \ {1}, unknown Commitment of input value ∈ {0,1}: • Choose random witness ← {1, … , − 1} • Compute , = ℎ ′ Binding: from ℎ = ℎ1− , we have ℎ1−2 = − Thus we have = log ℎ = −′ 1−2 ′ Impossible Cristina Onete || 24/10/2014 || 13 Pedersen Commitments = (, ) ∈ {0,1} …………………… Random , Alice Bob Check = (, ) Setup: ∗ = < >, prime field, ℎ = ∈ ∗ \ {1}, unknown Commitment of input value ∈ {0,1}: • Choose random witness ← {1, … , − 1} • Compute , = ℎ Hiding: Dist ≈ Dist (( ℎ)) Cristina Onete || 24/10/2014 || 14 DLog-based Commitments = (, ) ∈ …………………… Random , Alice Bob Check = (, ) Setup: prime, | ( − 1) prime, ∈ ∗ with ord = Commitment of input value ∈ : , = (no randomness) Computationally hiding: DLog Perfectly binding by construction Cristina Onete || 24/10/2014 || 15 Contents Commitment Schemes Sigma Protocols • Structure • Properties • Schnorr’s protocol Composition of Sigma Protocols • Parallel composition • AND composition • EQ and OR compositions The Fiat-Shamir heuristic Sigma Protocols: Structure Commitment: Witness Statement Challenge: ← {0,1} Prover Statement Verifier Response: Relation associated with NP-language L If (, )∈ , then is witness for E.g.: = , = , , , ℎ , ℎ = } Cristina Onete || 24/10/2014 || 17 Sigma Protocols: Properties Witness Statement Statement Prover Verifier Completeness: • Always accept prover with s.t. , ∈ (Special) soundness: • From , (, , ), and (, ′ , ′ ) with ≠ ′ can get with (, ) ∈ Honest verifier zero-knowledge (HVZK): • ∃ PPT Sim. s.t. , ← 0,1 Dist , , → (, , ) such that: ≈ Dist ′ , , ′ s. t. (, ) ∈ ) Cristina Onete || 24/10/2014 || 18 Schnorr’s Protocol Setup: prime, | ( − 1) prime, ∈ ∗ with ord = ← Prover ℎ = = ← Verifier = + ( ) ℎ = Check: = ℎ Completeness: = + = = = ( ) = ℎ ( ) Cristina Onete || 24/10/2014 || 19 Schnorr’s Protocol Setup: prime, | ( − 1) prime, ∈ ∗ with ord = ← = Prover ℎ = ← Verifier = + ( ) ℎ = Check: = ℎ Special Soundness: Given , , and , ′, ′ , with ≠ ′ find , , : = ℎ ( ) , ′, ′ : ′ = ℎ′ ( ) −′ = ℎ−′ → = Cristina Onete || ( − ′) ( − ′) 24/10/2014 || 20 Schnorr’s Protocol Setup: prime, | ( − 1) prime, ∈ ∗ with ord = ← Prover ℎ = = ← Verifier = + ( ) ℎ = Check: = ℎ HVZK: • ∃ , ← → (, , ) of same distribution • Simulator: generate ← . Now compute: = ℎ− ( ) • The conversation is valid and identically distributed Cristina Onete || 24/10/2014 || 21 Contents Commitment Schemes Sigma Protocols • Structure • Properties • Schnorr’s protocol Composition of Sigma Protocols • Parallel composition • AND composition • EQ and OR compositions The Fiat-Shamir heuristic Parallel Composition Goal: larger challenge space = (1 , 2 ) Witness Statement = (1, 2 ) Prover = (1, 2 ) Statement Verifier Verification is done in parallel: • Verify: (1 , 1 , 1 ) • Verify: (2 , 2 , 2 ) Accept iff. (1 , 1 , 1 ) and (2 , 2 , 2 ) Cristina Onete || 24/10/2014 || 23 AND Composition Goal: Proof for more than 1 witness = (1 , 2 ) w = (1 , 2 ) Statement Prover = (1, 2 ) Statement Verifier Verification is done as follows: • Verify: (1 , , 1 ) • Verify: (2 , , 2 ) Accept iff. (1 , , 1 ) and (2 , , 2 ) Cristina Onete || 24/10/2014 || 24 EQ-Composition Goal: Prove your witness fulfills two conditions = (1 , 2 ) Witness = (1 , 2 ) Prover = (1 , 2 ) Verifier Verification is done as follows: • Verify: (1 , , ) • Verify: (2 , , ) Accept iff. (1 , , ) and (2 , , ) Cristina Onete || 24/10/2014 || 25 OR-Composition Goal: the witness fulfills one of two conditions We won’t reveal which, however = ( 1 , 2 ) Either 1 or 2 = (1 , 2 ) Prover (1 , 1 , 2 , 2 ) Verifier = (1 , 2 ) Idea: split challenge in two, do one proof, simulate other Verification is done as follows: • Check: = 1 + 2 • Verify: (1 , 1 , 1 ) • Verify: (2 , 2 , 2 ) Accept iff. (1 , 1 , 1 ) and (2 , 2 , 2 ) and = 1 + 2 Cristina Onete || 24/10/2014 || 26 OR-Composition of Schnorr Setup: , | ( − 1) primes, 1 , 2 ∈ ∗ with ord 1 = ord 2 = = (1 , 2 ) 1 ℎ1 = 1 1 , ℎ2 = 2 2 Prover (1 , 1 , 2 , 2 ) Real Real Schnorr protocol run 1 1 , 2 2 Verifier Simulated • 1 ← • 2 , 2 ← • 1 = 1 • 1 = − 2 • 2 = 2 ℎ2 ? = 1 + 2 ? 1 = 1 ℎ11 ? 2 = 2 ℎ22 Simulation as in HVZK −2 • 1 = 1 + 1 1 Cristina Onete || 24/10/2014 || 27 Contents Commitment Schemes Sigma Protocols • Structure • Properties • Schnorr’s protocol Composition of Sigma Protocols • Parallel composition • AND composition • EQ and OR compositions The Fiat-Shamir heuristic The Fiat-Shamir Heuristic So far: interactive protocols, need random challenge If Prover can choose challenge, she can replay, she can choose = 0, or other convenient challenges Choose clever way to control challenge! Fiat-Shamir heuristic (, , ) Prover Verifier Verifier Prover Cristina Onete || 24/10/2014 || 29 Signatures from protocols Recall: SScheme = (KGen, Sign, Vf) Correctness: honest signatures should always verify Unforgeability: cannot sign fresh message without sk Setup: , | ( − 1) primes, ∈ ∗ with ord = ∈ ; = ← (, ) , ℎ = = + , = (, ) ℎ = Check: = ( ℎ− ) Secure if H outputs pseudorandom strings! Cristina Onete || 24/10/2014 || 30 Further reading Zero-Knowledge Proofs of Knowledge: S. Brands, ‘97: “Rapid Demonstration of Linear Relations Connected by Boolean Operators” U. Feige, A. Fiat, A. Shamir, ‘88: “Zero Knowledge Proofs of Identity” Trapdoor commitment schemes Di Crescenzo, Ishai, Ostrovsky, ‘98: “Non-interactive and NonMalleable Commitment” Fischlin, Fischlin, 2000: “Efficient Non-Malleable Commitment Schemes” Cristina Onete || 24/10/2014 || 31 Some exercises: Commitment schemes: • What if the receiver knows log ℎ for the Pedersen commitment? • What are the properties of the following commitment scheme? Setup: prime, | ( − 1) prime, ∈ ∗ with ord = Commit for ∈ < > : , = ( ) Sigma protocols: • Show that the following protocol is a Sigma protocol: Modulus = , order = ( − 1)( − 1), co-prime with ← ∗ ; = ← = Prover = = Verifier Cristina Onete || 24/10/2014 || 32 Some more exercises: • Is the following protocol a Sigma protocol? Setup: prime, | ( − 1) prime, ∈ ∗ with ord = ← ∗ ; ℎ = ℎ = ← Prover • = = + ( ) Verifier How can a malicious verifier find the value of in the protocol above? Cristina Onete || 24/10/2014 || 33 Thanks! CIDRE