close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
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
1/--страниц
Пожаловаться на содержимое документа