Rennes, 24/10/2014 Cristina OneteCIDRE/INRIA

Sigma Protocols and (Non-Interactive) Zero Knowledge

What is zero-knowledge?

Preuve à divulgation nulle de connaissance: “un protocole […] dans

lequel une entité […] prouve […] à une autre entité […] qu’une pro-

position est vraie sans […] révéler une autre information.”

Wikipedia, fr.wikipedia.org

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

Cristina Onete || 24/10/2014 || 2

So far

Prover Verifier

chg

resp

No anonymity:

Anonymity in a ring:

• or

𝑟𝑒𝑠𝑝=𝑅𝑆𝑖𝑔𝑛( h𝑐 𝑔) Anonymity and traceability:

𝑟𝑒𝑠𝑝=𝐺𝑆𝑖𝑔𝑛( h𝑐 𝑔) Now: Deniability/Zero-Knowledge!

Cristina Onete || 24/10/2014 || 3

Sigma () protocols

Prover Verifier

Setup: we have a secret witness and a public statement

and a function

Idea: Prover must prove she has such that

Group with p prime,

without revealing anything else

Example 1: finite fields

;

iff.

𝑦=𝑔𝑤

protocol

I know the discrete log of

Cristina Onete || 24/10/2014 || 4

Sigma () protocols

Prover Verifier

Setup: witness , statement , function Idea: Prover proves she has s.t. , but no more

Modulus , order , co-prime with

Example 2: RSA

;

iff.

𝑁 , 𝑦=𝑤𝑒𝑚𝑜𝑑𝑁

protocol

I know the message encrypted in

Cristina Onete || 24/10/2014 || 5

Sigma () protocols

Prover Verifier

Setup: witness , statement , function Idea: Prover proves she has s.t. , but no more

Example 3: Composition

; 𝑦={𝑦1 ,…, 𝑦𝑛}

protocol

I have the corresponding to one of

Group with p prime,

iff.

Cristina Onete || 24/10/2014 || 6

Contents

Sigma Protocols• Structure• Properties

Composition of Sigma Protocols

• Schnorr’s protocol

• Parallel composition• AND composition• EQ and OR compositions

The Fiat-Shamir heuristic

Commitment Schemes

Commitment Schemes

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?

Bob

Alice

Cristina Onete || 24/10/2014 || 8

Commitment Schemes

Alice Bob

Alice and Bob toss• Alice talks first

• Bob talks first

BobAlice

How can we avoid this?

Bob says he tossed the same value

Alice says she tossed the opposite value

Cristina Onete || 24/10/2014 || 9

Commitment Schemes

Alice Bob

Commitment: an envelope with a strange seal

• Alice talks first

• Commit phase: she hides toss in envelope, gives it to Bob

• Reveal phase: Alice tells Bob how to unseal envelope

• Bob reveals toss

Bob cleans

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

Alice Bob

Formally: 𝐶𝑜𝑚𝑚𝑖𝑡 :{0,1}𝑘×{0,1 }∗→{0,1 }∗

Commitment hiding:

Input 𝑎=𝐶𝑜𝑚𝑚𝑖𝑡 (𝑥 ,𝑤)

……………………𝑥 ,𝑤

Check

Random

Dist𝑤 (𝐶𝑜𝑚𝑚𝑖𝑡 (𝑥1 ,𝑤 ))≈ Dist𝑤 (𝐶𝑜𝑚𝑚𝑖𝑡 (𝑥2 ,𝑤))

Commitment binding:

∀ 𝑥1 ,𝑥2∈ {0,1 }∗ :Prob [ {𝑤 ,𝑤′ }← 𝜀 :𝐶𝑜𝑚𝑚𝑖𝑡 (𝑥1 ,𝑤 )=𝐶𝑜𝑚𝑚𝑖𝑡 (𝑥2 ,𝑤 ′) ]≪1

Cristina Onete || 24/10/2014 || 12

Pedersen Commitments

Setup: , prime field, \ , unknown

Commitment of input value :

Alice Bob

𝑥∈ {0,1 }Random

𝑎=𝐶𝑜𝑚𝑚𝑖𝑡 (𝑥 ,𝑤)

• Choose random witness

• Compute

……………………𝑥 ,𝑤

Check

Binding: from = we have

Thus we have Impossible

Cristina Onete || 24/10/2014 || 13

Pedersen Commitments

Setup: , prime field, \ , unknown

Commitment of input value :

Alice Bob

𝑥∈ {0,1 }Random

𝑎=𝐶𝑜𝑚𝑚𝑖𝑡 (𝑥 ,𝑤)

• Choose random witness

• Compute

……………………𝑥 ,𝑤

Check

Hiding:Dist𝑤 (𝐶𝑜𝑚𝑚𝑖𝑡 (𝑔𝑤 ) )≈ Dist𝑤(𝐶𝑜𝑚𝑚𝑖𝑡 (𝑔𝑤h))

Cristina Onete || 24/10/2014 || 14

DLog-based Commitments

Alice Bob

𝑥∈𝑍𝑞

Random

𝑎=𝐶𝑜𝑚𝑚𝑖𝑡 (𝑥 ,𝑤)……………………𝑥 ,𝑤

Check

Setup: prime, prime, with

Commitment of input value :

(no randomness)

Computationally hiding: DLog Perfectly binding by construction

Cristina Onete || 24/10/2014 || 15

Contents

Sigma Protocols• Structure• Properties

Composition of Sigma Protocols

• Schnorr’s protocol

• Parallel composition• AND composition• EQ and OR compositions

The Fiat-Shamir heuristic

Commitment Schemes

Sigma Protocols: Structure

Prover Verifier

Commitment:

Challenge:

Response:

E.g.:

Witness

Statement Statement

Relation associated with NP-language L If () , then is witness for

Cristina Onete || 24/10/2014 || 17

Sigma Protocols: Properties

Prover Verifier

𝑎𝑐𝑟

Completeness:

Witness

Statement Statement

• Always accept prover with s.t.

(Special) soundness:• From (), and () with can get with

Honest verifier zero-knowledge (HVZK):• PPT Sim. s.t. such that:

Dist𝑐 ( (𝑎 ,𝑐 ,𝑟 ) )≈ Dist𝑐 ( (𝑎′ ,𝑐 ,𝑟 ′ )|𝑤 s .t .(𝑤 , 𝑥)∈𝑅¿Cristina Onete || 24/10/2014 || 18

Schnorr’s Protocol

Prover Verifier

𝑎=𝑔𝑡𝑚𝑜𝑑𝑝

𝑐←𝑅𝑍𝑞

𝑟=𝑡+𝑐𝑤(𝑚𝑜𝑑𝑞) h=𝑔𝑤𝑚𝑜𝑑𝑝

Setup: prime, prime, with

𝑡←𝑅𝑍𝑞

Check:

Completeness:

𝑔𝑟=𝑔𝑡+𝑐𝑤¿𝑔𝑡𝑔𝑐𝑤=𝑎𝑔𝑐𝑤¿𝑎(𝑔¿¿𝑤)𝑐=𝑎 h𝑐 (𝑚𝑜𝑑𝑝)¿

Cristina Onete || 24/10/2014 || 19

Schnorr’s Protocol

Prover Verifier

𝑎=𝑔𝑡𝑚𝑜𝑑𝑝

𝑟=𝑡+𝑐𝑤(𝑚𝑜𝑑𝑞) h=𝑔𝑤𝑚𝑜𝑑𝑝

Setup: prime, prime, with

𝑡←𝑅𝑍𝑞

Check:

Special Soundness: Given and with find

: 𝑔𝑟− 𝑟 ′=h𝑐−𝑐 ′

: →𝑤=

(𝑟 −𝑟 ′ )(𝑐−𝑐 ′)

𝑐←𝑅𝑍𝑞

Cristina Onete || 24/10/2014 || 20

Schnorr’s Protocol

Prover Verifier

𝑎=𝑔𝑡𝑚𝑜𝑑𝑝

𝑟=𝑡+𝑐𝑤(𝑚𝑜𝑑𝑞) h=𝑔𝑤𝑚𝑜𝑑𝑝

Setup: prime, prime, with

𝑡←𝑅𝑍𝑞

Check:

HVZK: • of same distribution

• Simulator: generate . Now compute:

• The conversation is valid and identically distributed

𝑐←𝑅𝑍𝑞

Cristina Onete || 24/10/2014 || 21

Contents

Sigma Protocols• Structure• Properties

Composition of Sigma Protocols

• Schnorr’s protocol

• Parallel composition• AND composition• EQ and OR compositions

The Fiat-Shamir heuristic

Commitment Schemes

Parallel Composition

Goal: larger challenge space

Prover Verifier

𝑎=(𝑎¿¿1 ,𝑎2)¿

𝑐=(𝑐¿¿1 ,𝑐2)¿

𝑟=(𝑟 ¿¿1 ,𝑟2)¿

Witness

Statement Statement

Verification is done in parallel:

• Verify:

• Verify: Accept iff. and

Cristina Onete || 24/10/2014 || 23

AND Composition

Goal: Proof for more than 1 witness

Prover Verifier

𝑎=(𝑎¿¿1 ,𝑎2)¿

𝑐

𝑟=(𝑟 ¿¿1 ,𝑟2)¿

Statement Statement

Verification is done as follows:

• Verify:

• Verify: Accept iff. and

Cristina Onete || 24/10/2014 || 24

EQ-Composition

Goal: Prove your witness fulfills two conditions

Prover Verifier

𝑎=(𝑎1 ,𝑎2)

𝑐

𝑟

Witness

𝑥=(𝑥1 ,𝑥2) 𝑥=(𝑥1 ,𝑥2)

Verification is done as follows:

• Verify:

• Verify: Accept iff. and

Cristina Onete || 24/10/2014 || 25

OR-Composition

Goal: the witness fulfills one of two conditionsWe won’t reveal which, however

Prover Verifier

𝑎=(𝑎1 ,𝑎2)

𝑐

(𝑐1 ,𝑟1 ,𝑐2,𝑟2)

Either

𝑥=(𝑥1 ,𝑥2) 𝑥=(𝑥1 ,𝑥2)

Idea: split challenge in two, do one proof, simulate other

• Verify:

• Verify:

Verification is done as follows:

• Check:

Accept iff. and and𝑐=𝑐1+𝑐2

Cristina Onete || 24/10/2014 || 26

OR-Composition of Schnorr

Prover Verifier

𝑎=(𝑎¿¿1 ,𝑎2)¿

𝑐

(𝑐1 ,𝑟1 ,𝑐2,𝑟2)

𝑤1𝑔1𝑤1 ,𝑔2

𝑤2

Real Simulated

𝑐2 ,𝑟 2←𝑅𝑍𝑞

Setup: , primes, with

𝑎2=𝑔𝑟 2h2

−𝑐2𝑎1=𝑔𝑢1𝑚𝑜𝑑𝑝

𝑢1←𝑅𝑍 𝑞

𝑐1=𝑐−𝑐2𝑟1=𝑢1+𝑐1𝑤1

Simulationas in HVZK

?

?

?

Real Schnorr protocol run

Cristina Onete || 24/10/2014 || 27

Contents

Sigma Protocols• Structure• Properties

Composition of Sigma Protocols

• Schnorr’s protocol

• Parallel composition• AND composition• EQ and OR compositions

The Fiat-Shamir heuristic

Commitment Schemes

The Fiat-Shamir Heuristic

So far: interactive protocols, need random challenge

If Prover can choose challenge, she can replay, she can choose , or other convenient challenges

Prover Verifier

𝑎𝑐𝑟 Prover

𝑎𝑐𝑟Verifier

(𝑎 ,𝑐 ,𝑟 )

Fiat-Shamir heuristic

Choose clever way to control challenge!

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: , primes, with

𝑤 , h=𝑔𝑤 h=𝑔𝑤

𝑢∈𝑍𝑞 ;𝑎=𝑔𝑢

𝑐←𝐻 (𝑎 ,𝑀)

𝑀 ,𝜎=(𝑐 ,𝑟 )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 Connec-ted by Boolean Operators”

Trapdoor commitment schemes

Di Crescenzo, Ishai, Ostrovsky, ‘98: “Non-interactive and Non-Malleable Commitment”

U. Feige, A. Fiat, A. Shamir, ‘88: “Zero Knowledge Proofs of Identity”

Fischlin, Fischlin, 2000: “Efficient Non-Malleable Commitment Schemes”

Cristina Onete || 24/10/2014 || 31

Some exercises:

Commitment schemes:• What if the receiver knows for the Pedersen commitment?

• What are the properties of the following commitment scheme? Setup: prime, prime, with

Commit for :

Sigma protocols:• Show that the following protocol is a Sigma protocol:

Prover Verifier

𝑎=𝑢𝑒𝑚𝑜𝑑𝑁

Modulus , order , co-prime with

𝑢←𝑅 𝑍𝑁∗ ;

𝑐←𝑅𝑍 𝑒

𝑟=𝑢𝑤𝑐𝑚𝑜𝑑𝑁𝑦=𝑤𝑒𝑚𝑜𝑑𝑁

Cristina Onete || 24/10/2014 || 32

Some more exercises:

• Is the following protocol a Sigma protocol?

Setup: prime, prime, with

Prover Verifier

h=𝑔𝑤𝑚𝑜𝑑𝑝𝑎=𝑔𝑢𝑚𝑜𝑑𝑝𝑢←𝑅 𝑍𝑞

∗;

𝑐←𝑅𝑍 𝑐

𝑟=𝑐𝑢+𝑤 (𝑚𝑜𝑑𝑝)

• How can a malicious verifier find the value of in the protocol above?

Cristina Onete || 24/10/2014 || 33

CIDRE

Thanks!