Zuzana Trubini und Martin Hirt erhalten den TCC Test-of-Time Award

Das Preisvergabekomitee würdigt die Arbeit für die Einführung hyperinvertierbarer Matrizen, welche erhebliche Effizienzsteigerungen und schliesslich minimale Kommunikationskomplexität bei perfekt sicheren Mehrparteien-Berechnungen ermöglichen.

Die preisgekrönte Arbeit:

Eine hyperinvertierbare Matrix ist eine Matrix, bei der jede nicht-triviale quadratische Untermatrix invertierbar ist. Jede m-mal-n-Matrix induziert eine (lineare) Abbildung von n Eingabewerten auf m Ausgabewerte; wenn die Matrix hyperinvertierbar ist, dann hat die Abbildung die Eigenschaft, dass aus beliebigen n Werten (einige Eingaben und einige Ausgaben) die restlichen m Werte (einige Eingaben und einige Ausgaben) berechnet werden können.

Hyperinvertierbare Matrizen haben verschiedene Anwendungen in der Kryptographie. Betrachten wir zum Beispiel n Zufallswerte und einen Gegner, der t der Werte manipulieren kann: Ohne zu wissen, welches die manipulierten Werte sind, ist es möglich, n-t Werte zu extrahieren, die zufällig und dem Gegner unbekannt sind? Die Antwort ist ja, nämlich indem man eine hyperinvertierbare (n-t)-mal-n-Matrix auf die n Werte anwendet. Man kann zeigen, dass die n-t Ausgabewerte gleichmässig verteilt sind, statistisch unabhängig von den manipulierten Werten.

Eine weitere Anwendung ist die Überprüfung des Grades von Polynomen. Betrachten wir eine Menge von n Polynomen mit einem Grad von höchstens d, wobei der Gegner bis zu t der Polynome manipulieren und ihren Grad erhöhen kann. Eine solche Manipulation kann erkannt werden, indem man eine hyperinvertierbare n-mal-n-Matrix auf die Polynome anwendet, und den Grad von beliebigen t der Ausgabepolynome überprüft.

Die prämierte Arbeit stellt hyperinvertierbare Matrizen vor und zeigt, wie mit ihnen perfekt sichere Mehrparteien-Berechnungen mit linearen Kosten konstruiert werden können; d.h. für jede Multiplikation muss jede Partei nur eine konstante Anzahl von Werten verschicken.

Zuzana Trubini und Martin Hirt werden den TCC Test-of-Time Award im kommenden November erhalten.

Über Dr. Zuzana Trubini:

Zuzana Trubini studierte Mathematik an der ETH Zürich und promovierte in der Forschungsgruppe von Prof. Ueli Maurer. In ihrer Forschung konzentrierte sie sich auf kryptographische Protokolle und Mehrparteien-Berechnung in synchronen und asynchronen Netzwerken. Ihre Ergebnisse wurden an renommierten internationalen Konferenzen wie TCC, Asiacrypt, und PODC veröffentlicht. Zurzeit arbeitet sie bei cnlab security AG als Sicherheitsanalystin.

Über Dr. Martin Hirt:

Martin Hirt hat einen Masterabschluss in Informatik und einen Doktortitel in Kryptographie, beide von der ETH Zürich. Letzteren erwarb er 2001. Seine Forschung konzentriert sich auf kryptographische Protokolle, Effizienzsteigerungen, asynchrone Netzwerke, verallgemeinerte Gegenmodelle und elektronische Abstimmungen. Hirts Arbeiten wurde an verschiedenen angesehenen Konferenzen wie TCC, Crypto und Eurocrypt veröffentlicht. Zurzeit arbeitet er als leitender Forschungsassistent und Dozent am Institut für Theoretische Informatik der ETH Zürich.