Rational Cryptography

Bei der Definition der Sicherheit für gemeinsame Berechnungen mehrerer Parteien wird in der Kryptographie üblicherweise vorausgesetzt, dass ehrliche Parteien, d. h. Parteien, die sich an das vorgeschriebene Protokoll halten, nicht durch Angreifer gestört werden können. Bei einer sicheren Berechnung einer Blind-Auktion wird beispielsweise sichergestellt, dass alle ehrlichen Parteien den korrekten Sieger der Auktion als konsistentes Ergebnis erhalten, während ihre Gebote geheim bleiben. Bei diesem Ansatz werden die Teilnehmer in ehrliche und beliebig böswillige separiert. In der Realität haben wir es jedoch oft mit Situationen zu tun, in denen jede Partei einen gewissen Gewinn aus der Ausführung eines Protokolls zieht und versucht, diesen Gewinn zu maximieren. Bei einer Auktion beispielsweise möchte jeder Bieter so wenig wie möglich bezahlen und gleichzeitig das angebotene Gut erhalten. In diesem Szenatio gibt es keine von Natur aus ehrlichen oder böswilligen Parteien, sondern nur rationale Parteien, die den Gewinn maximieren wollen. Die rationale Kryptographie konzentriert sich auf solche Szenarien.

Konkret werden in der rationalen Kryptographie Konzepte wie Gewinn und Rationalität formalisiert, wobei Techniken aus dem Bereich der Spieltheorie verwendet werden. Außerdem beantworten wir die Frage, ob es geeignete Protokolle gibt, denen solche rationalen Parteien von Natur aus folgen (die überraschende Antwort lautet: Ja, solche Protokolle gibt es!). Wenn Sie mit Spieltheorie einigermaßen vertraut sind, denken Sie an Nutzenfunktionen, um die Gewinne der Parteien zu modellieren, Strategien welche aus arbiträren Computerprogrammen bestehen und an den Entwurf von Protokollen, die (Nash-)Gleichgewichten entsprechen, selbst wenn einige Parteien zusammenarbeiten. Nicht zuletzt erlaubt uns die Annahme rationaler Parteien manchmal, Szenarien zu modellieren, die in der traditionellen Kryptographie problematisch sind, z. B. das Münzwerfen zwischen zwei Parteien.

Bleiben wir zur Veranschaulichung beim Münzwurf. Stellen Sie sich ein Szenario vor, in dem Alice und Bob jeweils eine andere Aktivität für den Abend vorschlagen. Sie einigen sich darauf, diese durch virtuelles Werfen einer Münze auszuwählen. Bei Kopf gewinnt Alice, andernfalls gewinnt Bob. Das heißt, ihr Gewinn hängt nur vom Ergebnis des Münzwurfs ab. Um ihren Gewinn zu erhöhen, haben beide einen rationalen Anreiz, die Münze in Richtung des ihnen zugewiesenen Symbols zu lenken. Herkömmliche kryptografische Protokolle für das Münzwerfen erlauben es in der Regel, das Wurfergebnis durch folgenden Angriff zu beeinflussen: Eine Partei, zum Beispiel Alice, erhält zunächst das Ergebnis und entscheidet dann, ob sie es veröffentlicht oder das Protokoll beendet und Bob ohne Ergebnis zurücklässt. In unserem Szenario würde Alice das Ergebnis nur bekannt geben, wenn das Resultat Kopf ist, und andernfalls das Protokoll beenden. Wissend, dass Alice in unserem rationalen Kontext Kopf bevorzugt, können wir unser Protokoll jedoch so gestalten, dass vorzeitiger Abbruch und jegliches andere abweichende Verhalten durch Wahl von Zahl bestraft wird. Da ein detektiertes Abweichen vom Protokoll nun zu einem schlechteren Ergebnis für Alice führt, ist es rational nicht vom Protokoll abzuweichen.

Wir forschen derzeit an geeigneten Modellen für das recht junge Gebiet der rationalen Kryptographie. Dazu gehört auch die Forschung zur Anpassung spieltheoretischer Begriffe an die Kryptographie, was nicht immer problemlos möglich ist. Dies ist insbesondere der Fall, da diese Begriffe für Situationen entwickelt wurden, in denen die Strategieräume oft sehr begrenzt sind und Annahmen über die Rechenleistung keine Rolle spielen. Außerdem sind wir daran interessiert, effiziente Protokolle für reale Anwendungen in rationalen Kontexten zu entwerfen, wie z.B. stabile Matchings.