Praktische Sichere Mehrparteienberechnung

Das Forschungsgebiet der sicheren Mehrparteienberechnung hat seinen Ursprung in Yaos Millionärsproblem [Yao86]:

Wie können zwei sich gegenseitig misstrauende Millionäre herausfinden, wer von ihnen reicher ist, ohne dass sie sich gegenseitig irgendeine weitergehende Information über den konkreten Wert ihres Besitzes offenlegen?

Abstrakt gesehen sind zwei Parteien (Alice und Bob) gegeben: Alice kennt eine geheime Zahl x, Bob kennt eine geheime Zahl y und sie wollen berechnen, welche der beiden Zahlen größer ist. Allerdings soll Bob dabei außer der Information, ob x<y oder x≥y, nichts weiter über x lernen und analog Alice nichts weiter über y.

Die Verallgemeinerung dieses Problems ist recht naheliegend: Statt der Information, ob x<y bzw. x≥y, wird eine beliebige Funktion f(x,y) berechnet und es können auch mehr als zwei Parteien an der Berechnung teilnehmen (die Funktion f muss dann natürlich entsprechend viele Argumente haben). Die Sicherheitsforderung besteht in diesem allgemeinen Fall darin, dass keine Partei P, selbst wenn sie sich beliebig bösartig verhält, etwas über die geheimen Eingaben der anderen Parteien lernt, was nicht direkt aus der Eingabe von P und dem öffentlichen Funktionsergebnis f(x,y,...) berechnet werden kann.

In der Literatur finden sich verschiedene Techniken und Lösungsansätze für sichere Mehrparteien-Berechnungen, welche auf unterschiedlichen Sicherheitsannahmen beruhen; z.B. dass sich eine Mehrheit der teilnehmenden Parteien ehrlich an alle vorgeschriebenen Abläufe hält, oder dass bereits initial eine Public-Key-Infrastruktur gegeben ist.

Wir untersuchen die Schnittmenge zwischen Protokollen, die sich effizient praktisch anwenden lassen, und Protokollen, die beweisbar sicher in einem für Theoretiker interessanten Modell sind. Hierbei sind insbesondere Protokolle im Universal Composability (UC) Framework für uns interessant, da diese allgemein durch die starken Sicherheitsgarantien den Ruf haben ineffizient zu sein. Jedoch werden auch Protokolle in anderen Frameworks betrachtet.

Neben maßgeschneiderten Protokollen für eine bestimmte Problemstellung ist ebenfalls für uns interessant, mit welchen Grundbausteinen sich allgemeine Berechnungen möglichst effizient durchführen lassen.

Wir bieten in jedem Sommersemester die Vorlesung „Kryptographische Protokolle“ an. Darin werden neben Bausteinen wie Commitments, Zero-Knowledge Beweise und Oblivious Transfer Protokollen insbesondere unterschiedliche Ansätze zur sicheren Mehrparteienberechnung vorgestellt und auf deren Sicherheit eingegangen. Wir setzen Grundlagenwissen im Bereich der Kryptographie voraus, wie sie in der Vorlesung „Theoretische Grundlagen der Kryptographie” vermittelt werden, die in jedem Wintersemester angeboten wird.

Wir bieten zudem unregelmäßig die Vorlesung „Kryptographische Wahlverfahren” an. Anhand des Anwendungsfalls der Wahl von Parteien oder Personen werden darin zunächst die Anforderungen an kryptographische Wahlverfahren besprochen und auf diesen Anwendungsfall zugeschnittene Protokolle vorgestellt und analysiert. Erste Vorkenntnisse zu Signaturen, Commitments, Hashfunktionen, Zero-Knowledge Beweisen und Public-Key Verschlüsselung werden vorausgesetzt. Wir empfehlen dafür die Vorlesung „Theoretische Grundlagen der Kryptographie”, die jährlich im Wintersemester angeboten wird.