Das Bit-Commitment nach Blum

Man nehme den Münzwurf als Beispiel.

Alice möchte gegenüber Bob ein Commitment abgeben. Die möglichen Nachrichten Kopf oder Zahl, also $1$ oder $0$ [2] [3]:

Bob:	Alice:
	Setup: Alice wählt zwei Primzahlen $p$ und $q$ via Multiplikation beider erhält sie $n$ sie wählt ein $vϵQNR_{n}^{+1}$
	Commiten: Alice wählt ihr Nachrichtenbit $b$ wählt eine Zufallszahl $rϵZ_n^*$ erstellt das Commitment $c=r^2v^b$ sendet $n$ , $c$ und $v$ an Bob
empfängt $n$ , $c$ und $v$
	Aufdecken: Alice sendet $p$ , $q$ , $r$ und $b$ an Bob
Bob empfängt $p$ , $q$ , $r$ und $b$
Bob testet ob $p$ und $q$ Primzahlen sind und ob gilt: $r \in Z_n^$ , $n=pq$ und $c=r^2 v^b$

Erklärung:

$Z_n^*$ sind positive Ganzzahlen kleiner als und Modulo $n$
aus $Z_n^*$ nehme man alle Quadrate und definiere sie als Gruppe $QR_n$
Man bilde das Jakobi-Symbol:
- $J_{n}^{+1}=\{x \in Z_n^* | (x/n)=1\}$
- durch $QNR_n^{+1}=J_n^{+1}⁄QR_n$ erhält man alle Nichtquadrate aus $J_n^{+1}$

$v$ darf kein Quadrat sein,denn die Auflösung ist wie folgt:

$b=0$ : $c=r^2$ , also ein Quadrat
$b=1$ : $c=r^2 v$ , also kein Quadrat
$=>$ wenn $v$ ein Quadrat wäre,könnte über $b$ keine Aussage getroffen werden

Um festzustellen, ob v tatsächlich ein Quadrat ist, benötigt Bob $p$ und $q$ . Diese können nicht aus $n$ gewonnen werden.

Da gilt:
$b=0$ : $c=r^2$ , also ein Quadrat
$b=1$ : $c=r^2 v$ , also kein Quadrat

ist Alice an ihr Commitment unconditional gebunden.

Bob könnte das Jacobi-Symbol nur berechnen, wenn er $p$ und $q$ kennen würde. Wenn er allerdings herausfinden könnte ob zufälliges Element in $J_n^{+1}$ ein Quadrat ist, könnte er auf $b$ schließen. Das würde aber enorme Rechenleistung fordern, weswegen das Verfahren computational hiding ist.