Das Pedersen Commitment

Für viele Anwendungen wird ein wesentlich größerer Zahlenbereich für die Nachricht benötigt, als nur ein Bit. Unter anderem für Kartenspiele. Ein Deck enthält 52 verschiedene Karten, eine Nachricht muss also mindestens 52 unterschiedliche Werte haben können. Ein noch schwierigeres Beispiel ist aber Stein-Schere-Papier. Mit den drei Werten Stein, Schere, Papier hat es genau einen Wert zu viel für das Bit-Commitment. Wir haben also die Gefahr, dass Bob Alices Wert aus dem Commitment durch Durchprobieren finden kann. Eine Lösung für dieses Problem wurde 1991 von Torben Pryds Pedersen vorgestellt. Sie funktioniert wie folgt [2] [4]:

Bob:	Alice:
Setup: Bob wählt zufällige Primzahlen $p$ und $q$ , wobei $p-1$ ein Vielfaches von $q$ ist wählt zufällig $g$ und $v$ aus einer Untergruppe $G_q$ der Ordnung $q$ in $Z_p^*$ außerdem: $g≠1$ und $v≠1$ Bob sendet $g$ , $q$ , $g$ und $v$ an Alice
	Alice empfängt $g$ , $q$ , $g$ und $v$
	Committen: Alice testet, ob $p$ und $q$ Primzahlen und ob $p-1$ ein Vielfaches von $q$ ist. Außerdem ob $g$ und $v$ aus einer Untergruppe $G_q$ der Ordnung $q$ in $Z_p^*$ sind. Für den Commit wählt sie eine Zufallszahl $r \in {0,…,q-1}$ und die Nachricht $m \in {0,…,q-1}$ Daraus wird das Commitment $c$ berechnet: $c= g^r v^m$ und an Bob gesendet
Bob empfängt $c$
	Aufdecken: Alice sendet $r$ und $m$ an Bob
Bob empfängt $r$ und $m$ Bob testet ob<br/> $c= g^r v^m$ Wenn $c≠ g^r v^m$ hat Alice geschummelt.

Erklärung:

Warum darf $m$ und $r$ nicht größer als $q-1$ sein? Jedes Element der Untergruppe $G_q$ ist ein Generator. Es wird das folgende mathematische Problem als Einwegfunktion genutzt:

$m⟼ g^m \ mod\ p$

Zu beachten ist aber Folgendes: Die Gruppe $G_q$ ist zyklisch:

$g^0=1$ und $g^q=1$
$g^{q+1}=g^1$
$1\ mod\ p=1$

Der Sinn von $r$ ist, die Nachricht $m$ zu maskieren (ebenso wie in Commitment mit Hash-Funktion, Möglichkeit 2).

Bob könnte, wenn der Wertebereich klein genug wäre, alle Möglichkeiten durchprobieren. Bei Stein-Schere-Papier sähe das folgendermaßen aus:

sei $m=3$ und $c= g^m$

Probieren:
$c≠g^1$
$c≠g^2$
$c=g^3=>m=3$

Jedoch bei

sei $m=3$ und $c=g^r v^m$

Probieren:
$c=g^r v^1$
$c=g^r v^2$
$c=g^r v^3=>m$ bleibt unbekannt

Auch hier sorgt $r$ , das aus demselben Bereich wie $m$ ist, dafür dass selbst wenn der diskrete Logarithmus gelöst werden könnte, immer noch alle Werte für $m$ gleich wahrscheinlich wären. Deswegen ist das Verfahren unconditional hiding.

Eventuelle Probleme: Kann Alice für ein Commitment $c$ von $m$ ein $m'$ an Bob senden, das ungleich $m$ ist? Dazu müsste gelten:

$g^r v^m=g^{r'} v^{m'}$
$log_g(v)=(m'-m)^{-1} (r-r')$

Da Alice theoretisch fähig wäre, den Logarithmus zu lösen, was mit großen Zahlen sehr rechenaufwendig und zeitaufwendig ist, ist das Verfahren computational binding. Aber: Bob setzt die Werte $p$ und $q$ . Deswegen hat er direkten Einfluss darauf, wie stark Alice an ihren Wert gebunden ist. Bob sollte damit, um seinetwillen, Primzahlen im Bitbereich $>1024$ wählen.

Des Weiteren kann Bob die Zeit zwischen Committen und Aufdecken begrenzen, was für eine Berechnung von $m'$ und $r'$ , die $c$ ergeben würden, eine gewaltige Rechenleistung erfordern würde.

Eine Rechenleistung, die in absehbarer Zeit nicht gegeben sein wird.