Institut für Theoretische Informatik (ITI)

Praktische Sichere Mehrparteienberechnung

Beschreibung

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, nichts ü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.

Unsere Forschung

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.

Unsere Lehre

Referenzen:

[Yao86] Andrew Chi-Chih Yao: How to Generate and Exchange Secrets (Extended Abstract). FOCS 1986: 162-167