"Effiziente Implementierung der Optimierung von sicheren Berechnungen" | (Efficient Implementation of Secure Computation Optimization)

Date

Jul 12, 2012

Time

10:00 AM - 11:00 AM

Speaker

Raphael Urmoneit

Affiliation

Institut für Systemarchitektur, Datenschutz und Datensicherheit

Language

de

Main Topic

Informatik

Other Topics

Informatik

Description

Es gibt eine Anzahl praktischer Fälle, in denen die sogenannte Mehrparteienberechnung notwendig oder hilfreich ist. Dabei handelt es sich um eine besondere Form der Berechnung einer Funktion, bei der mehrere Parteien jeweils eine Funktionseingabe beisteuern. Das Ergebnis soll allen Parteien bekannt gemacht werden. Die Sicherheitsanforderung der Mehrparteienberechnung ist, dass dennoch keine Partei die Eingabe der anderen Parteien nach der Berechnung kennt. Zum Erstellen solcher Protokolle existieren einige Compiler, die die gemeinsame Berechnung sicher bewerkstelligen, d.h. dass keine Partei hinterher die Eingaben der anderen Parteien erschließen kann. Der bekannteste Compiler heißt Fairplay von Malkhi et al. [1]. Der Nachteil eines solchen Compilers ist, dass der resultierende Programmcode im Allgemeinen nicht optimiert ist und demzufolge lange Laufzeiten hat. Kerschbaum hat ein automatisches Optimierungsverfahren vorgestellt [2], mit dem man den Programmcode generisch optimieren kann. Dieses Optimierungsverfahren soll in der Bachelorarbeit in die Praxis umgesetzt werden. Zunächst werden die Schritte des Verfahrens erläutert. 1) Das Programm liegt in der vereinfachten SFDL-Sprache vor (SFDL siehe http://www.cs.huji.ac.il/labs/danss/Fairplay/UFairplay.ppt) 2) Mithilfe von JavaCC (http://javacc.java.net/) und JJTree (http://www.cs.kent.ac.uk/teaching/resources/java/javacc/DOC/JJTree.html) wird der Code analysiert 3) Kerschbaums Optimierungsverfahren: Mithilfe von Modallogik werden sicherheitskritische und -unkritische Programmsegmente ermittelt. Der Theorembeweiser Isabelle (http://www.cl.cam.ac.uk/research/hvg/isabelle/dist/Isabelle2011-1/doc/tutorial.pdf) kann zum Einsatz kommen. 4) Die sicherheitskritischen Segmente werden durch einen Aufruf der Fairplay-Routine in eine sichere Funktionsberechnung übersetzt und die sicherheitsunkritischen Teile können lokal berechnet werden. Das Verfahren soll anhand eines Beispiels erläutert werden. Dabei handelt es sich um eine Berechnung des gemeinsamen Medians zweier sortierter Listen. Im einfachsten Fall erstellen zwei Parteien Alice und Bob jeweils ein zwei-elementiges Integer-Array. Die Zahlen sollen paarweise verschieden sein und innerhalb eines Arrays geordnet vorliegen. Die zu berechnende Funktion ist Folgende: als Ausgabe soll ein mittleres Element des vereinten Arrays von Alice und Bob ermittelt werden. In der Bachelorarbeit soll der Optimierer (Schritt 3) effizient implementiert werden. Dazu sind die Regeln von Modallogik in eine einfachere, dem Theorem Prover zugängliche Logik umzusetzen. Das dazu notwendige Programmgerüst und Algorithmus sind zu entwickeln und zu implementieren. Mittels der erstellten Regeln ist der Theorem Prover aufzurufen und die Ergebnisse für die Zwischensprache verwendbar zu machen. Das dazu notwendige Verfahren soll anhand des oben beschriebenen Beispiels Schritt für Schritt in der Arbeit beschrieben werden. Im Nachwort sei darauf hingewiesen werden, dass das in der Arbeit vorgestellte Verfahren zur Umsetzung von Kerschbaums Optimierungsideen lediglich den Kernteil zur Erstellung eines vollständigen Compilers darstellt. Wenn man das Verfahren um die nötigen Schritte erweitert, kann man einen Compiler bauen, der dem Fairplay-Compiler ähnlich ist, allerdings die Optimierungsideen implementiert. Somit würde er im Vergleich zu Fairplay stark optimierten Code erzeugen. [1] D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay—a secure two-party computation system. In Proceedings of the 13th USENIX Security Symposium, 2004. [2] F. Kerschbaum. Automatically optimizing secure computation. In Proceedings of the 18th ACM Conference on Computer and Communications Security, 2011.

Last modified: Jul 12, 2012, 9:35:58 AM