Kryptografische Protokolle

Bit-Commitment

 aufwärts

Commitment bedeutet Festlegung. Bei einer öffentlichen Aus­schreibung beispiels­weise legt jeder Anbieter sich auf sein Angebot fest, gibt dieses aber zunächst noch nicht preis (indem er es in einem ver­schlossenen Umschlag abgibt). Erst nach Ende der Aus­schreibungsfrist wird die Festlegung offenbart (der Umschlag geöffnet). Gewähr­leistet ist so, dass während der Aus­schreibung die Konkurrenten nichts über die Höhe der Angebote der anderen erfahren und dass die Angebote verbindlich sind, d.h. nachträglich nicht mehr geändert werden können.

Im Folgenden geht es darum, wie sich eine solche Festlegung (zunächst nur auf ein Bit 0 oder 1) mit krypto­grafischen Verfahren realisieren lässt.

Werfen einer Münze

Das Werfen einer Münze kann, wenn gerade keine Münze zur Hand ist, wie folgt realisiert werden. Jeder der beiden Teilnehmer A und B denkt sich eine Zahl aus der Menge {0, 1}. Sind die beiden gedachten Zahlen gleich, hat A gewonnen, sind sie verschieden, hat B gewonnen.

Das Problem ist, dass sich A und B die Zahlen mitteilen müssen, um zu entscheiden, wer gewonnen hat. Sagt B als erster zum Beispiel: "Ich habe die 1", so könnte A versucht sein, zu antworten: "Tja, tut mir leid, ich habe auch die 1", obwohl er sie gar nicht hatte.

Die Lösung besteht in folgendem Protokoll.

A schreibt seine Zahl auf einen Zettel und legt den Zettel verdeckt auf den Tisch. A hat sich damit auf seine Zahl festgelegt, aber B kennt die Zahl noch nicht. Nun erst nennt B seine Zahl. Daraufhin offenbart A seine Festlegung, indem er den Zettel zeigt. B prüft, welche Zahl auf dem Zettel steht.

Auch hier gibt es Möglich­keiten zu täuschen. So könnte B beispiels­weise versuchen, heimlich unter den Zettel zu schauen. Oder A könnte versuchen, nachdem er B's Zahl erfahren hat, den Zettel gegen einen anderen auszu­tauschen, bevor er ihn zeigt.

Bei der krypto­grafischen Realisierung dieses Protokolls müssen ent­sprechende Täuschungs­möglichkeiten aus­geschlossen werden.

Bit-Commitment-Protokoll

Das Problem bei der krypto­grafischen Realisierung ist, wie sich A auf ein Bit i Element {0, 1} festlegen kann, ohne dieses Bit preiszugeben, und wie er anschließend beweisen kann, dass er sich tatsächlich auf dieses Bit festgelegt hatte. Diese Aufgabe wird als commitment (verbindliche Festlegung) bezeichnet.

Bei dem folgenden Protokoll (Bild 1) werden zwei isomorphe Graphen zugrunde­gelegt. Für dieses Protokoll ist es wichtig, dass A keinen Iso­morphismus zwischen den beiden Graphen kennt. Dies ist gewähr­leistet, wenn B die beiden Graphen erzeugt und den Iso­morphismus geheimhält, und wenn die Graphen so groß sind, dass die Berechnung des Iso­morphismus praktisch undurch­führ­bar ist.

   
         A           B
 isomorphe Graphen
   G0 und G1
 
wählt zufällig
   i Element {0, 1} und
   Isomorphismus h
  
berechnet
   H = h(Gi)
 
Festlegung
 
  
  (versucht, die
Festlegung aufzudecken)
   
 
 wählt
   j Element {0, 1}
   
(versucht, die
Festlegung zu fälschen)
 Offenbaren der
Festlegung
 
  
  prüft
  
 obh-1(H) = G0  folgt i = 0)
 oder  h-1(H) = G1folgt i = 1)
Bild 1: Bit-Commitment-Protokoll

Das Protokoll besteht im wesentlichen aus zwei Phasen, der Festlegung und dem Offenbaren der Festlegung. Zwischendurch sendet B das Bit j, das er gewählt hat.

Sicherheit des Protokolls

In der ersten Phase legt sich Teilnehmer A auf i Element {0, 1} fest, indem er einen zufälligen Iso­morphismus h auf den ent­sprechenden Graphen Gi anwendet und das Ergebnis, den Graphen H, an Teilnehmer B sendet.

Um heraus­zufinden, auf welches i sich A festgelegt hat, müsste B herausfinden, ob H aus G0 oder aus G1 hervor­gegangen ist. Dies ist jedoch unmöglich, da G0 und G1 isomorph sind.

Es ist also für Teilnehmer B unmöglich, die Festlegung vorzeitig aufzudecken.

Nachdem B sein Bit j gesendet hat, offenbart nun Teilnehmer A in der zweiten Phase die Festlegung, indem er den verwendeten Iso­morphismus an B sendet. Teilnehmer B berechnet h-1(H) und weiß nun, auf welches i sich A festgelegt hatte, je nachdem, ob das Ergebnis G0 oder G1 ist.

Teilnehmer A kann jedoch versuchen zu täuschen, indem er einen Iso­morphismus g sendet, für den gilt g -1(H) = Gjj ≠ i. Einen solchen Iso­morphismus g zu finden, ist aber mindestens genauso schwer, wie einen Iso­morphismus zwischen G0 und G1 zu finden, denn es gilt

Gj  =  g -1(H)  =  g -1(h(Gi)).

D.h. wenn A den Iso­morphismus g hat, dann hat er auch den Iso­morphismus zwischen Gi und Gj, nämlich f = hg -1 (Bild 2).

Bild 2: Isomorphismen zwischen Gi , Gj und H
Bild 2: Isomorphismen zwischen Gi , Gj und H

Das Problem, einen Iso­morphismus f zwischen zwei isomorphen Graphen zu bestimmen, ist jedoch schwer zu lösen. Es ist kein Verfahren bekannt, dessen Rechen­aufwand polynomiell bezogen auf die Anzahl der Knoten der Graphen ist.

Es ist also für Teilnehmer A praktisch undurch­führ­bar, die Festlegung zu fälschen.

Realisierung des Münzwurfs

 

Das Werfen einer Münze wird mit Hilfe des angegebenen Bit-Commitment-Protokolls also wie folgt realisiert:

  1. A legt sich auf i Element {0, 1} fest;
  2. B wählt j Element {0, 1};
  3. A hat gewonnen, wenn er durch Offenbaren der Festlegung beweisen kann, dass er sich auf i = j festgelegt hatte; ansonsten hat B gewonnen.

Im nächsten Abschnitt wird gezeigt, wie sich aus diesem Bit-Commitment-Protokoll ein Protokoll zur Teilnehmer-Authentifizierung ableiten lässt.

Literatur

[BNS 05]A. Beutelspacher, H.B. Neumann, T. Schwarzpaul: Kryptografie in Theorie und Praxis. Vieweg (2005)

 

Weiter mit:   [Zero-Knowledge-Protokoll zur Teilnehmer-Authentifizierung]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 23.11.2003   Updated: 11.06.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik