## Вход

Забыли?

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

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