Commitment-Verfahren

Ein Commitment-Verfahren ist ein kryptographisches Zwei-Parteien-Protokoll, das es einer Partei ermöglicht, sich gegenüber der anderen Partei auf einen Wert festzulegen, ohne etwas über diesen Wert zu verraten. Später kann dieser Wert dann aufgedeckt werden.^[1] Ein Commitment-Verfahren kann damit verglichen werden, einen Zettel mit dem Wert in eine verschlossene Kiste zu legen und dem Empfänger die Kiste zu geben. Ohne den Schlüssel kann der Empfänger nichts über den Wert auf dem Zettel erfahren. Der Sender kann den Wert nicht mehr verändern, da sich die Kiste nicht mehr in seinem Besitz befindet. Zum Aufdecken schickt der Sender dem Empfänger den Schlüssel zu der Kiste. Commitment-Verfahren sind wichtige Primitive, die beispielsweise in sicheren Mehrparteienberechnungen oder Zero-Knowledge-Protokollen angewendet werden.

Eine klassische Anwendung für ein Commitment ist der Münzwurf via Telefon.^[2] Alice und Bob wollen eine Münze werfen, aber weil die beiden sich über die Telefonverbindung nicht sehen können und sich gegenseitig nicht vertrauen wollen, funktioniert das übliche Protokoll „einer sagt an, der andere wirft“ nicht. Eine mögliche Lösung wäre, dass Alice ihre Wahl einem vertrauenswürdigen Dritten mitteilt, der dann, nachdem Bob das Ergebnis mitgeteilt hat, den Gewinner bestimmt. Mit einem Bit-Commitment lässt sich das Problem ohne dritte Partei lösen, indem Alice ein Commitment auf ihre Wahl an Bob schickt. Bob kann aus dem Commitment nichts über Alices Wahl lernen, aber Alice ist nun festgelegt und kann ihre Wahl nicht nachträglich ändern. Nun wirft Bob die Münze und teilt Alice das Ergebnis mit, woraufhin Alice das Commitment öffnet. Damit kennen beide den Gewinner. Eine Realisierung ist zum Beispiel über kryptographische Hashfunktionen möglich.

Beschreibung

Ein Commitment-Verfahren besteht aus zwei Phasen. In der ersten wird das Commitment erzeugt, mit dem sich Alice auf einen Wert festlegt. In der zweiten Phase wird das Commitment aufgedeckt. Damit das Verfahren korrekt ist, wird gefordert, dass der ursprüngliche Wert nach dem Aufdecken des Commitments wiederhergestellt sein muss (Viability).

Commit-Phase

Alice generiert zu dem Wert, auf den sie sich festlegen möchte, ein Commitment und eine Zusatzinformation, die das Aufdecken erlaubt. Oft ist diese Zusatzinformation der Zufall, der bei der Erzeugung des Commitments verwendet wurde. Sie schickt das Commitment an Bob und ist nun auf den Wert festgelegt, während Bob aus dem Commitment nichts darüber lernt.

Reveal-Phase

Alice schickt nun ihren Wert und die Zusatzinformation an Bob. Bob kann nun nachvollziehen, dass das Commitment tatsächlich zu dem Wert gehört.

Sicherheitseigenschaften

Binding

Es darf nicht möglich sein, ein Commitment nachträglich auf einen anderen Wert aufzudecken.

Hiding

Das Commitment darf keinen Rückschluss auf den Wert zulassen, auf den sich die Partei festgelegt hat.

Einzelnachweise

1. Gilles Brassard, David Chaum, and Claude Crépeau: Minimum Disclosure Proofs of Knowledge. In: Journal of Computer and System Sciences. Band 37, 1988, S. 156–189 (mcgill.ca [PDF]).
2. Manuel Blum: Coin Flipping by Telephone. In: Proceedings of CRYPTO. 1981, S. 11–15 (cmu.edu [PDF]).