Commitment mit Hash-Funktion

Eine Möglichkeit ein Commitment durchzuführen, wäre die Nutzung einer kollisionsfreien Hash-Funktion, hier gibt es mehrere Möglichkeiten, welche aber einige Probleme bereiten:

Man nehme als Beispiel das Spiel Stein-Schere-Papier. Die Werte Stein, Schere und Papier werden als die Zahlen 1,2 und 3 codiert.

Für alle Beispiele gilt:
Kollisionsfreie Hashfunktion sei $h()$
Commitment sei $c$

1.Möglichkeit:
Nachricht sei $m ∈{1,2,3}$

Problem: Da die Anzahl der Werte, die m annehmen kann begrenzt ist, kann Bob durch Probieren auf das richtige Ergebnis kommen:

Sei: $m=3$ und Bob kennt $h()$ und $c$.

$c=h(1)→falsch$
$c=h(2)→falsch$
$c=h(3)→richtig=>m=3$

Bob kennt $m$ schon vor dem Aufdecken und kann mit diesem Wissen betrügen. Das Verfahren wird erst dann computational hiding, wenn die Anzahl der Werte, die $m$ annehmen kann, so hoch ist, dass ein Durchprobieren aller, mit aktueller Rechenleistung nicht mehr in absehbarer Zeit zu bewerkstelligen ist.

Jedoch: *So lange die Hashfunktion $h()$ kollisionsfrei ist, ist das Verfahren unconditional binding:
$m'$ sei eine Nachricht, ungleich der übermittelten Nachricht $m$.
Damit gilt für alle $m'≠m$: $c ≠h(m')$

Die zweite Möglichkeit:
Die Nachricht sei wieder $m ∈{1,2,3}$

Vorteil: Da Alice eine Zufallszahl $r$ aus derselben Menge der möglichen Ergebnisse nimmt, maskiert sie ihre Nachricht $m$. Bob kann alle Möglichkeiten durchprobieren, wird aber herausfinden, dass so lange er $r$ nicht kennt, jede Nachricht $m$ gleich wahrscheinlich ist. Woraus folgt, dass das Commitment unconditional hiding ist.

Problem: Da Alice die Zufallszahl $r$ und die Nachricht $m$ beim Setup und Aufdecken frei wählen kann, kann sie einfach betrügen:

Es gilt:
$r'*m'=r*m$
$=>c=h(r'*m' )=h(r*m)$

Das Commitment ist damit nicht bindend.

Die dritte Möglichkeit:
Nachricht sei wieder $m∈{1,2,3}$

Eventuelle Probleme:
Annahme: Bob möchte Schummeln. Es wird davon ausgegangen, dass die Hashfunktion $h()$ kollisionsfrei ist, also könnte er alle möglichen Werte von $m$ und $r$ durchprobieren und würde auf das Commitment $c$ stoßen, womit das Verfahren nicht länger hiding wäre. Da in diesem Fall $r$ nicht an den Zahlenraum von $m$ gebunden ist, kann $r$ jeden beliebigen Wert annehmen, die Anzahl der Möglichkeiten ist also nur durch die verwendete Hardware beschränkt. Mit normalen Ressourcen kann Bob nicht alle Möglichkeiten durchprobieren, mit unendlicher Rechenpower aber schon. Deswegen ist dieses Verfahren nur computational hiding.

Alice versucht, $m'$ und $r$' zu finden, mit denen sie schummeln kann, allerdings gilt immer noch, dass $h()$ kollisionsfrei ist und deswegen gilt:

$h(m)||h(r)≠h(m' )||h(r')$
$=> c ≠h(h(m')||h(r'))$

Das Commitment ist theoretisch unconditional binding. In der Praxis ist der Wertebereich der Ausgabe einer Hashfunktion endlich, während die Eingabe unendlich viele Werte haben kann. Denn es gilt für eine Hashfunktion mit fester Länge der Ausgabe:

Eingabe $I$ kann unendlich viele Werte annehmen
Länge der Ausgabe $O$ sei $n$
Der Zahlenraum der Ausgabe $O$ ist damit $O ∈{0,…,2^n}$

Dem Geburtstagsparadoxon nach, würden erste Kollisionen auftreten, wenn $\sqrt{(2^n)}$ unterschiedliche Eingaben $I$ gehasht worden sind. Das heißt es müssen Kollisionen existieren. Daher kann eine Kollision bei unendlicher Zeit oder Rechenleistung gefunden werden, weswegen die Möglichkeiten 1 und 3 in der Praxis nur computational binding sind.

In den vorangegangenen Beispielen konnte die Nachricht mehrere Werte haben. Was aber, wenn die Nachricht nur ein Bit lang ist? Da bei so einem begrenzten Raum von $m$, das in diesem Beispiel ein Bit ist und deswegen $b$ genannt werden wird, nur noch $2×r_{max}$ Möglichkeiten probiert werden müssten, ist das vorherige Verfahren für Bits ungeeignet.

Deswegen nun ein weiteres Verfahren: Das Bit-Commitment nach Blum.