51
0 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings FAKULTÄT FÜR INFORMATIK, INSTITUT FÜR THEORETISCHE INFORMATIK Digitale Signaturen sEUF-CMA & Pairings | Gunnar Hartung, Björn Kaidel KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft www.kit.edu

Digitale Signaturen - sEUF-CMA & Pairings | Gunnar Hartung ... · 0 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings FAKULTÄT FÜR INFORMATIK, INSTITUT FÜR THEORETISCHE

Embed Size (px)

Citation preview

0 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

FAKULTÄT FÜR INFORMATIK, INSTITUT FÜR THEORETISCHE INFORMATIK

Digitale SignaturensEUF-CMA & Pairings | Gunnar Hartung, Björn Kaidel

KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft www.kit.edu

Socrative: Wiederholung

1 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

https://b.socrative.com/login/student/Room: SIGNATUREN

Kann man aus jeder CH eine Einmalsig. konstruieren?Kann man aus jeder Einmalsig. eine CH konstruieren?Def. von Kollision bei CH?Verstärkung von EUF-CMA?

Werbung: Algorithmen 1 Tutoren gesucht!

2 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Prof. Müller-Quade liest im SS 2017 „Algorithmen 1“Übungsleiter: Björn KaidelWir suchen Tutoren/innen!Anstellung vom 01.04 bis 31.07.2017Aufgaben: Übungsblätter korrigieren, Tutorien halten (ein Tutorium proWoche)Vorraussetzung: Bestandene "Algorithmen 1" Klausur

Interesse? Mail an [email protected]!

Frage vom letzten Mal - EUF-CMA 2. Variante

3 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

EUF-CMA Variante 2CEUF-CMA A

(pk , sk)← Gen(1k )

(ch, τ)← GenCH(1k )

pk , ch

mi , chi

σi ← Sign(sk ,mi , chi )σi

Anfragen nacheinanderq = q(k) Anfragenq Polynom

m∗ , σ∗

Vfy(pk ,m∗, σ∗, ch) = 1?∧

m∗ /∈ {m1, . . . ,mq}?

Frage: Kann man das nicht mit der DLog-CH erreichen, indem manH(m) statt m signiert? (H Hashfunktion)

EUF-CMA 2. Variante (Antwort)

4 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Frage: Kann man das nicht mit der DLog-CH erreichen, indem manH(m) statt m signiert? (H Hashfunktion)Antwort: Nein!

A erhält ch = (g,h) vom Challenger.A wählt zwei Nachrichten m1 6= m2

A generiert chA = (gH(m2)/H(m1),h)Dies ist eine gültige CH-Fkt.!

A lässt m1 mit chA signieren und erhält Signatur σ = (σ′, r ). Es gilt

chA(H(m1), r ) = gH(m2)·H(m1)/H(m1) · hr = gH(m2) · hr = ch(H(m2), r )

Damit ist σ eine gültige Signatur für m2 bzgl. ch

EUF-CMA 2. Variante (Antwort)

4 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Frage: Kann man das nicht mit der DLog-CH erreichen, indem manH(m) statt m signiert? (H Hashfunktion)Antwort: Nein!

A erhält ch = (g,h) vom Challenger.A wählt zwei Nachrichten m1 6= m2

A generiert chA = (gH(m2)/H(m1),h)Dies ist eine gültige CH-Fkt.!

A lässt m1 mit chA signieren und erhält Signatur σ = (σ′, r ). Es gilt

chA(H(m1), r ) = gH(m2)·H(m1)/H(m1) · hr = gH(m2) · hr = ch(H(m2), r )

Damit ist σ eine gültige Signatur für m2 bzgl. ch

EUF-CMA 2. Variante (Antwort)

4 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Frage: Kann man das nicht mit der DLog-CH erreichen, indem manH(m) statt m signiert? (H Hashfunktion)Antwort: Nein!

A erhält ch = (g,h) vom Challenger.A wählt zwei Nachrichten m1 6= m2

A generiert chA = (gH(m2)/H(m1),h)Dies ist eine gültige CH-Fkt.!

A lässt m1 mit chA signieren und erhält Signatur σ = (σ′, r ). Es gilt

chA(H(m1), r ) = gH(m2)·H(m1)/H(m1) · hr = gH(m2) · hr = ch(H(m2), r )

Damit ist σ eine gültige Signatur für m2 bzgl. ch

Socrative-Fragen vom letzten Mal

5 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Hinweis: immer mehr Fragen online! :)(Bitte nicht nur diese Fragen zur Prüfungsvorbereitung verwenden!)

„Wann wurden CH-Funktionen zum ersten Mal definiert?“1998, in [KR98]

„Das kleine r an der Tafel sieht aus wie ein µ!“Soµµy! Veµsuche mich zu besseµn!

„Signaturverfahren darf NUR für Chamäleon-Signaturen verwendetwerden, da jeder der Signatur hat, UUF-Angriffe trivial durchführenkann.“

Frage war mir nicht ganz klar... Fragesteller anwesend?

Socrative-Fragen vom letzten Mal

5 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Hinweis: immer mehr Fragen online! :)(Bitte nicht nur diese Fragen zur Prüfungsvorbereitung verwenden!)

„Wann wurden CH-Funktionen zum ersten Mal definiert?“1998, in [KR98]

„Das kleine r an der Tafel sieht aus wie ein µ!“Soµµy! Veµsuche mich zu besseµn!

„Signaturverfahren darf NUR für Chamäleon-Signaturen verwendetwerden, da jeder der Signatur hat, UUF-Angriffe trivial durchführenkann.“

Frage war mir nicht ganz klar... Fragesteller anwesend?

Socrative-Fragen vom letzten Mal

5 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Hinweis: immer mehr Fragen online! :)(Bitte nicht nur diese Fragen zur Prüfungsvorbereitung verwenden!)

„Wann wurden CH-Funktionen zum ersten Mal definiert?“1998, in [KR98]

„Das kleine r an der Tafel sieht aus wie ein µ!“

Soµµy! Veµsuche mich zu besseµn!

„Signaturverfahren darf NUR für Chamäleon-Signaturen verwendetwerden, da jeder der Signatur hat, UUF-Angriffe trivial durchführenkann.“

Frage war mir nicht ganz klar... Fragesteller anwesend?

Socrative-Fragen vom letzten Mal

5 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Hinweis: immer mehr Fragen online! :)(Bitte nicht nur diese Fragen zur Prüfungsvorbereitung verwenden!)

„Wann wurden CH-Funktionen zum ersten Mal definiert?“1998, in [KR98]

„Das kleine r an der Tafel sieht aus wie ein µ!“Soµµy! Veµsuche mich zu besseµn!

„Signaturverfahren darf NUR für Chamäleon-Signaturen verwendetwerden, da jeder der Signatur hat, UUF-Angriffe trivial durchführenkann.“

Frage war mir nicht ganz klar... Fragesteller anwesend?

Socrative-Fragen vom letzten Mal

5 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Hinweis: immer mehr Fragen online! :)(Bitte nicht nur diese Fragen zur Prüfungsvorbereitung verwenden!)

„Wann wurden CH-Funktionen zum ersten Mal definiert?“1998, in [KR98]

„Das kleine r an der Tafel sieht aus wie ein µ!“Soµµy! Veµsuche mich zu besseµn!

„Signaturverfahren darf NUR für Chamäleon-Signaturen verwendetwerden, da jeder der Signatur hat, UUF-Angriffe trivial durchführenkann.“

Frage war mir nicht ganz klar... Fragesteller anwesend?

Inhalt

6 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

sEUF-CMA durch Chamäleon-Hashing (Kap. 3.6)

Pairing-basierte Signaturen (Kap. 5)

EUF-CMA - Verstärken?

7 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

CEUF-CMA A

(pk , sk)← Gen(1k ) pk

mi

σi

Anfragen nacheinanderq = q(k) Anfragenq Polynom

m∗ , σ∗

Ver (pk ,m∗, σ∗) = 1?∧

m∗ /∈ {m1, . . . ,mq}?

A gewinnt, falls Vfy(pk ,m∗, σ∗) = 1 und m∗ /∈ {m1, ...,mq}

Frage: Stärkerer Sicherheitsbegriff als EUF-CMA?

sEUF-CMA - Sicherheitsexperiment

8 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

CsEUF-CMA A

(pk , sk)← Gen(1k ) pk

mi

σi

Anfragen nacheinanderq = q(k) Anfragenq Polynom

m∗ , σ∗

Ver (pk ,m∗, σ∗) = 1?∧

(m∗, σ∗) /∈ {(m1, σ1) . . . , (mq , σq)}?

A gewinnt, falls Vfy(pk ,m∗, σ∗) = 1 und(m∗, σ∗) /∈ {(m1, σ1) . . . , (mq , σq)}

Definition: sEUF-CMA

9 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Def. 51: (sEUF-CMA)Ein digitales Signaturverfahren Σ = (Gen, Sign,Vfy) istsEUF-CMA-sicher , falls für alle PPT A gilt, dass

Pr[ACsEUF-CMA(pk) = (m∗, σ∗) : Vfy(pk ,m∗, σ∗) = 1∧

(m∗, σ∗) /∈ {(m1, σ1), ..., (mq , σq)}

]im Sicherheitsparameter k vernachlässigbar ist.

sEUF-CMA: Anwendungen

10 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

A kann nun auch gewinnen, wenn zu m∗ eine Signaturanfragegesendet hat...... dann muss σ∗ aber neu sein

Hauptsächlich als Baustein für komplexe Krypto-AnwendungenBeispielsweise um IND-CCA2-sichere PKE zu konstruieren

CH + EUF-CMA→ sEUF-CMA (Skript)

11 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

EUF-CMA Σ′ = (Gen′, Sign′,Vfy′)CH-Fkt. CH = (GenCH,TrapCollCH)

Konstruiere sEUF-CMA-sicheres Σ = (Gen, Sign,Vfy).

Seien m′, σ′ zufällige Werte, aber fest Gen(1k ) :(pk ′, sk ′)← Gen′(1k )

(chF , τF )← GenCH(1k )

(chH , τH)← GenCH(1k )

pk = (pk ′, chF , chH)

sk = (sk ′, τH)

CH + EUF-CMA→ sEUF-CMA (Skript)

11 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

EUF-CMA Σ′ = (Gen′, Sign′,Vfy′)CH-Fkt. CH = (GenCH,TrapCollCH)

Konstruiere sEUF-CMA-sicheres Σ = (Gen, Sign,Vfy).

Seien m′, σ′ zufällige Werte, aber fest Gen(1k ) :(pk ′, sk ′)← Gen′(1k )

(chF , τF )← GenCH(1k )

(chH , τH)← GenCH(1k )

pk = (pk ′, chF , chH)

sk = (sk ′, τH)

CH + EUF-CMA→ sEUF-CMA (Skript)

12 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Seien m′, σ′ zufällige Werte, aber fest

Sign(sk ,m) : sk = (sk ′, τH)

rF ← R, r ′H ← Rh := chH(m′‖σ′, r ′H)m̃ := chF (h, rF )σ̃← Sign′(sk ′, m̃)

rH ← TrapCollCH(τH , (m′‖σ′, rH),m‖σ̃)σ := (σ̃, rF , rH)

Vfy(pk ,m, σ): pk = (pk ′, chF , chH), σ = (σ̃, rF , rH)h := chH(m‖σ̃, rH)m̃ := chF (h, rF )

Vfy′(pk ′, m̃, σ̃)?= 1

CH + EUF-CMA→ sEUF-CMA (Skript)

12 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Seien m′, σ′ zufällige Werte, aber fest

Sign(sk ,m) : sk = (sk ′, τH)

rF ← R, r ′H ← Rh := chH(m′‖σ′, r ′H)m̃ := chF (h, rF )σ̃← Sign′(sk ′, m̃)

rH ← TrapCollCH(τH , (m′‖σ′, rH),m‖σ̃)σ := (σ̃, rF , rH)

Vfy(pk ,m, σ): pk = (pk ′, chF , chH), σ = (σ̃, rF , rH)h := chH(m‖σ̃, rH)m̃ := chF (h, rF )

Vfy′(pk ′, m̃, σ̃)?= 1

CH + EUF-CMA→ sEUF-CMA (Skript)

13 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Theorem:Σ ist sEUF-CMA-sicher, wenn CH kollisionsresistent und Σ′

EUF-CMA-sicher ist.

Beweisidee: Siehe TafelAnm.: Konstruktion mit Sicherheitsbeweis findet sich in [SPW07]

(Konstruktion im Skript leicht anders!)

Transformationen: Übersicht (Skript)

14 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

EUF-naCMA EUF-1-naCMA

EUF-CMA

CH

sEUF-CMA

SUF-naCMAdieses Jahrnicht be-sprochen

Transformationen: Übersicht (Skript)

14 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

EUF-naCMA EUF-1-naCMA

EUF-CMA

CH

sEUF-CMA

SUF-naCMAdieses Jahrnicht be-sprochen

Transformationen: Übersicht (Skript)

14 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

EUF-naCMA EUF-1-naCMA

EUF-CMA

CH

sEUF-CMA

SUF-naCMAdieses Jahrnicht be-sprochen

Transformationen: Übersicht (Skript)

14 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

EUF-naCMA EUF-1-naCMA

EUF-CMA

CH

sEUF-CMA

SUF-naCMAdieses Jahrnicht be-sprochen

Transformationen: Übersicht (Skript)

14 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

EUF-naCMA EUF-1-naCMA

EUF-CMA

CH

sEUF-CMA

SUF-naCMAdieses Jahrnicht be-sprochen

Socrative: sEUF-CMA

15 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

https://b.socrative.com/login/student/Room: SIGNATUREN

Ist jede EUF-CMA-sichere und deterministische SignatursEUF-CMA-sicher?Wie unterscheiden sich EUF-CMA und sEUF-CMA?Welche Transformationen wurden in der VL besprochen?

Pairings

16 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Definition 78 (Pairings):Seien G1,G2,GT zyklische Gruppen mit Ordnung p prim. Ein Pairing(bilineare Abbildung) ist eine Abbildung

e : G1 ×G2 → GT

mit den Eigenschaften:

1) Bilinearität: ∀g1,g′1 ∈ G1,g2,g′2 ∈ G2 :

e(g1 · g′1,g2) = e(g1,g2) · e(g′1,g2)

e(g1,g2 · g′2) = e(g1,g2) · e(g1,g′2)

⇒ e(ga1 ,g2) = e(g1,g2)

a = e(g1,ga2)

Ermöglicht eine Multiplikation im Exponenten.

Pairings

16 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Definition 78 (Pairings):Seien G1,G2,GT zyklische Gruppen mit Ordnung p prim. Ein Pairing(bilineare Abbildung) ist eine Abbildung

e : G1 ×G2 → GT

mit den Eigenschaften:1) Bilinearität: ∀g1,g′1 ∈ G1,g2,g′2 ∈ G2 :

e(g1 · g′1,g2) = e(g1,g2) · e(g′1,g2)

e(g1,g2 · g′2) = e(g1,g2) · e(g1,g′2)

⇒ e(ga1 ,g2) = e(g1,g2)

a = e(g1,ga2)

Ermöglicht eine Multiplikation im Exponenten.

Pairings

16 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Definition 78 (Pairings):Seien G1,G2,GT zyklische Gruppen mit Ordnung p prim. Ein Pairing(bilineare Abbildung) ist eine Abbildung

e : G1 ×G2 → GT

mit den Eigenschaften:1) Bilinearität: ∀g1,g′1 ∈ G1,g2,g′2 ∈ G2 :

e(g1 · g′1,g2) = e(g1,g2) · e(g′1,g2)

e(g1,g2 · g′2) = e(g1,g2) · e(g1,g′2)

⇒ e(ga1 ,g2) = e(g1,g2)

a = e(g1,ga2)

Ermöglicht eine Multiplikation im Exponenten.

Pairings

17 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

2) Nicht-Ausgeartetheit (engl. non-degenerate, auchNicht-Degeneriertheit)Für Erzeuger g1 ∈ G1,g2 ∈ G2 gilt:

e(g1,g2) ist Erzeuger von GT|GT |prim⇔ e(g1,g2) 6= 1

3) Effiziente Berechenbarkeit

Anm.: Es gibt auch Pairings mit Gruppen ohne Primordnung! (spielen indieser VL keine Rolle)

Pairings

17 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

2) Nicht-Ausgeartetheit (engl. non-degenerate, auchNicht-Degeneriertheit)Für Erzeuger g1 ∈ G1,g2 ∈ G2 gilt:

e(g1,g2) ist Erzeuger von GT|GT |prim⇔ e(g1,g2) 6= 1

3) Effiziente Berechenbarkeit

Anm.: Es gibt auch Pairings mit Gruppen ohne Primordnung! (spielen indieser VL keine Rolle)

Pairings

17 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

2) Nicht-Ausgeartetheit (engl. non-degenerate, auchNicht-Degeneriertheit)Für Erzeuger g1 ∈ G1,g2 ∈ G2 gilt:

e(g1,g2) ist Erzeuger von GT|GT |prim⇔ e(g1,g2) 6= 1

3) Effiziente Berechenbarkeit

Anm.: Es gibt auch Pairings mit Gruppen ohne Primordnung! (spielen indieser VL keine Rolle)

Pairing: Anmerkungen

18 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

G1,G2 in der Regel elliptische Kurven („Ursprungsgruppen“)GT ⊆ FQ („Target-Gruppe“)

Ursprüngliche Anwendung:KryptoanalyseBsp: Ist Dlog in GT einfacher als in Gi , kann e helfen, den Dlog zuberechnen

gx , x gesuchtberechne e(gx ,g) = e(g,g)x und dann Dlog von e(g,g)x

Manche Annahmen (wie DDH) gelten in solchen Gruppen nicht!

Pairing: Anmerkungen

18 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

G1,G2 in der Regel elliptische Kurven („Ursprungsgruppen“)GT ⊆ FQ („Target-Gruppe“)

Ursprüngliche Anwendung:KryptoanalyseBsp: Ist Dlog in GT einfacher als in Gi , kann e helfen, den Dlog zuberechnen

gx , x gesuchtberechne e(gx ,g) = e(g,g)x und dann Dlog von e(g,g)x

Manche Annahmen (wie DDH) gelten in solchen Gruppen nicht!

Typen von Pairings

19 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Typ 1: G1 = G2, „symmetrisches Pairing“e : G×G→ GT

Typ 2: G1 6= G2, „asymmetrisches Pairing“Es existiert effizienter, nicht-trivialer Homomorphismus

ψ : G2 → G1

Typ 3: G1 6= G2, „asymmetrisches Pairing“Es existiert kein effizienter, nicht-trivialer Homomorphismus

ψ : G2 → G1

Anm: In der VL betrachten wir hauptsächlich „symmetrische Pairings“!

Typen von Pairings

19 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Typ 1: G1 = G2, „symmetrisches Pairing“e : G×G→ GT

Typ 2: G1 6= G2, „asymmetrisches Pairing“Es existiert effizienter, nicht-trivialer Homomorphismus

ψ : G2 → G1

Typ 3: G1 6= G2, „asymmetrisches Pairing“Es existiert kein effizienter, nicht-trivialer Homomorphismus

ψ : G2 → G1

Anm: In der VL betrachten wir hauptsächlich „symmetrische Pairings“!

Typen von Pairings

19 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Typ 1: G1 = G2, „symmetrisches Pairing“e : G×G→ GT

Typ 2: G1 6= G2, „asymmetrisches Pairing“Es existiert effizienter, nicht-trivialer Homomorphismus

ψ : G2 → G1

Typ 3: G1 6= G2, „asymmetrisches Pairing“Es existiert kein effizienter, nicht-trivialer Homomorphismus

ψ : G2 → G1

Anm: In der VL betrachten wir hauptsächlich „symmetrische Pairings“!

Typen von Pairings

19 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Typ 1: G1 = G2, „symmetrisches Pairing“e : G×G→ GT

Typ 2: G1 6= G2, „asymmetrisches Pairing“Es existiert effizienter, nicht-trivialer Homomorphismus

ψ : G2 → G1

Typ 3: G1 6= G2, „asymmetrisches Pairing“Es existiert kein effizienter, nicht-trivialer Homomorphismus

ψ : G2 → G1

Anm: In der VL betrachten wir hauptsächlich „symmetrische Pairings“!

Pairings: Forschung

20 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Pairings bereits „sehr mächtig“Multi-lineare Abbildung wären sehr starkes Werkzeug!Man kannte bis vor wenigen Jahren keine Kandidaten für solche Abb.2012: Garg, Gentry, Halevi „Candidate Multilineaer Maps from IdealLattices and Applications“ [GGH12]Seitdem viele Kandidaten, Angriffe, Konstruktionen die multilineareAbb. verwenden...Sehr turbulentes Forschungsfeld!

Joux’s 3-Parteien Schlüsselaustausch

21 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

Grundprinzip wie beim Diffie-Hellman-Schlüsselaustausch für 2Parteien3 Parteien A, B, CEinfaches Anwendungsbeispiel für Pairingse : G×G→ GT , g Erzeuger von G, |G| = |GT | = p prim.

Joux’s 3-Parteien Schlüsselaustausch

22 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

A

B C

a← Zp

b ← Zp c ← Zp

ga g a

ga ga

gb

gb

gb

ga,gbg c

gc

gb,gc

ga,gc

k = e(gb,gc)a = e(g,g)abc

k = e(ga,gc)b = e(g,g)abc k = e(ga,gb)c = e(g,g)abc

Gemeinsamer Schlüssel ist k = e(g,g)abc

Nachrichtenaustausch muss nicht nacheinander sein!(über multilineare Abb. auf größere Anzahl Parteien erweiterbar)

Joux’s 3-Parteien Schlüsselaustausch

22 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

A

B C

a← Zp

b ← Zp c ← Zp

ga g a

ga ga

gb

gb

gb

ga,gbg c

gc

gb,gc

ga,gc

k = e(gb,gc)a = e(g,g)abc

k = e(ga,gc)b = e(g,g)abc k = e(ga,gb)c = e(g,g)abc

Gemeinsamer Schlüssel ist k = e(g,g)abc

Nachrichtenaustausch muss nicht nacheinander sein!(über multilineare Abb. auf größere Anzahl Parteien erweiterbar)

Joux’s 3-Parteien Schlüsselaustausch

22 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

A

B C

a← Zp

b ← Zp c ← Zpg

a g a

ga ga

gb

gb

gb

ga,gbg c

gc

gb,gc

ga,gc

k = e(gb,gc)a = e(g,g)abc

k = e(ga,gc)b = e(g,g)abc k = e(ga,gb)c = e(g,g)abc

Gemeinsamer Schlüssel ist k = e(g,g)abc

Nachrichtenaustausch muss nicht nacheinander sein!(über multilineare Abb. auf größere Anzahl Parteien erweiterbar)

Joux’s 3-Parteien Schlüsselaustausch

22 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

A

B C

a← Zp

b ← Zp c ← Zp

ga g a

ga

ga

gb

gb

gb

ga,gb

g cgc

gb,gc

ga,gc

k = e(gb,gc)a = e(g,g)abc

k = e(ga,gc)b = e(g,g)abc k = e(ga,gb)c = e(g,g)abc

Gemeinsamer Schlüssel ist k = e(g,g)abc

Nachrichtenaustausch muss nicht nacheinander sein!(über multilineare Abb. auf größere Anzahl Parteien erweiterbar)

Joux’s 3-Parteien Schlüsselaustausch

22 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

A

B C

a← Zp

b ← Zp c ← Zp

ga g a

ga ga

gb

gb

gb

ga,gbg c

gc

gb,gc

ga,gc

k = e(gb,gc)a = e(g,g)abc

k = e(ga,gc)b = e(g,g)abc k = e(ga,gb)c = e(g,g)abc

Gemeinsamer Schlüssel ist k = e(g,g)abc

Nachrichtenaustausch muss nicht nacheinander sein!(über multilineare Abb. auf größere Anzahl Parteien erweiterbar)

Joux’s 3-Parteien Schlüsselaustausch

22 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

A

B C

a← Zp

b ← Zp c ← Zp

ga g a

ga ga

gb

gb

gb

ga,gb

g cgc

gb,gc

ga,gc

k = e(gb,gc)a = e(g,g)abc

k = e(ga,gc)b = e(g,g)abc k = e(ga,gb)c = e(g,g)abc

Gemeinsamer Schlüssel ist k = e(g,g)abc

Nachrichtenaustausch muss nicht nacheinander sein!(über multilineare Abb. auf größere Anzahl Parteien erweiterbar)

Joux’s 3-Parteien Schlüsselaustausch

22 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

A

B C

a← Zp

b ← Zp c ← Zp

ga g a

ga ga

gb

gb

gb

ga,gb

g cgc

gb,gc

ga,gc

k = e(gb,gc)a = e(g,g)abc

k = e(ga,gc)b = e(g,g)abc k = e(ga,gb)c = e(g,g)abc

Gemeinsamer Schlüssel ist k = e(g,g)abc

Nachrichtenaustausch muss nicht nacheinander sein!(über multilineare Abb. auf größere Anzahl Parteien erweiterbar)

Socrative: Pairings

23 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

https://b.socrative.com/login/student/Room: SIGNATUREN

Was impliziert die Bilinearität von Pairings?Wieviele Parteien können an Joux’s Schlüsselaustausch teilnehmen?Müssen in Joux’s Schlüsselaustausch die Nachrichten nacheinanderverschickt werden?

References I

24 2017-01-20 B. Kaidel – Digitale Signaturen: sEUF-CMA & Pairings

S. Garg, C. Gentry, and S. Halevi. “Candidate MultilinearMaps from Ideal Lattices and Applications”. In: IACRCryptology ePrint Archive 2012 (2012), p. 610. URL:http://eprint.iacr.org/2012/610.

H. Krawczyk and T. Rabin. “Chameleon Hashing andSignatures”. In: IACR Cryptology ePrint Archive 1998 (1998),p. 10. URL: http://eprint.iacr.org/1998/010.

R. Steinfeld, J. Pieprzyk, and H. Wang. “How to StrengthenAny Weakly Unforgeable Signature into a StronglyUnforgeable Signature”. In: Topics in Cryptology - CT-RSA2007, The Cryptographers’ Track at the RSA Conference2007, San Francisco, CA, USA, February 5-9, 2007,Proceedings. 2007, pp. 357–371. DOI: 10.1007/11967668_23.URL: http://dx.doi.org/10.1007/11967668_23.