TU Darmstadt / ULB / tuprints

Secure Computations on Non-Integer Values

Franz, Martin :
Secure Computations on Non-Integer Values.
TU Darmstadt
[Ph.D. Thesis], (2011)

[img]
Preview
PDF
Dissertation-MartinFranz.pdf
Available under Simple publication rights for ULB.

Download (494Kb) | Preview
Item Type: Ph.D. Thesis
Title: Secure Computations on Non-Integer Values
Language: English
Abstract:

Die Forschung zu Secure Multiparty Computation (SMC) begann im Jahr 1982, als Andrew C. Yao das Millionärsproblem vorstellte. Seitdem hat die Wissenschaft in diesem Bereich große Fortschritte gemacht, viele sicherheitskritische Anwendungen wurden mittels SMC realisiert. Einzig die Anwendungen, die mathematische Berechnungen auf nicht-ganzzahligen Werten durchführen, waren lange Zeit von diesen Fortschritten ausgeschlossen. Zu diesen Anwendungen gehören beispielsweise Algorithmen, die Berechnungen auf großen Intervallen mit reellen Zahlen durchführen.

Die vorliegende Dissertation präsentiert neue Ergebnisse in diesem Forschungsbereich. Zunächst wird eine neue Methode vorgestellt, die es erlaubt, sichere Berechnungen auf reellen Zahlen durchzuführen, die in einer logarithmischen Repräsentierung gespeichert sind. Zum einen wird beschrieben, wie so repräsentierte Zahlen effektiv verschlüsselt werden können. Danach werden kryptographische Protokolle angegeben, die es erlauben bestimmte arithmetische Operationen mit auf diese Weise kodierten und verschlüsselten Werten durchzuführen.

In einem weiteren Kapitel wird eine sichere Umsetzung des IEEE 754 Gleitkommastandards präsentiert. Diese zeigt auf, wie Gleitkommazahlen verschlüsselt werden können. Zudem werden kryptographische Protokolle beschrieben, die es erlauben Berechnungen auf solch verschlüsselten Gleitkommazahlen durchzuführen.

Abgeschlossen wird diese Dissertation mit sowohl einer theoretischen, als auch einer praktischen Evaluierung der hier vorgestellten Techniken. Zunächst werden in einer ausgiebigen theoretischen Komplexitätsanalyse die Rechen- wie auch die Kommunikationskomplexität der beiden neu vorgestellten Methoden zum Rechnen mit verschlüsselten Zahlen vorgestellt. Danach wird die Performanz dieser beiden Methoden mit einer Standardmethode verglichen, die auf einer Festpunktarithmetik basiert. Es zeigt sich, dass beide Methoden für typische Probleme deutlich effizienter sind als die Festpunktarithmetik.

Zum Abschluss wird auch die praktische Machbarkeit der neu vorgestellten Techniken demonstriert. Dafür wurden zwei wichtige Algorithmen aus der Bioinformatik implementiert, der Forward- und der Viterby Algorithmus. Diese Algorithmen sind typischerweise numerisch instabil, denn sie führen ihre Berechnungen auf ständig kleiner werdenden Wahrscheinlichkeiten durch. Die hier vorgestellte Implementierung zeigt, dass die neuen theoretischen Methoden auch in der Praxis erfolgreich eingesetzt werden können, um real vorkommende Probleme zu lösen.

Alternative Abstract:
Alternative AbstractLanguage
Research in the scientific field of \textit{Secure Multiparty Computation} (SMC) was started in the year 1982, when Andrew C. Yao presented the well known Millionaires' problem. Since then, this area of research has witnessed many new theoretical results and technological advances, which made it possible to realize a large scale of applications using techniques from SMC. However, one class of applications has barely been touched in the past 25 years: The question of how to perform secure computations with non-integer values, e.g. with values in a floating point representation on large intervals taken from the domain of real values. This thesis presents new results in this field of research. Our first contribution is a new computational framework for SMC with real values which are stored in a logarithmic encoding. This includes on the one hand a representation scheme which allows to encrypt values stored in this representation. On the other hand, our computational framework consists of secure protocols that allow to perform all arithmetic operations on encrypted values encoded in this representation scheme. Next, we present a secure and efficient implementation of the IEEE 754 floating point standard. Our approach shows how to encrypt floating point values in a way that all arithmetic operations, including the normalization operation, can be performed interactively between two mutually distrusting parties with acceptable computational and communication overhead. We round off this dissertation with both a theoretical and a practical evaluation of the proposed techniques. Firstly, we give a thorough theoretical complexity analysis which compares the two approaches in terms of computational and communication complexity. We further compare the two different approaches with a basic scheme for a fixed point representation, showing that both approaches indeed outperform the fixed point representation for computational problems of typical size. Finally, we demonstrate the practical importance of the presented techniques. For this, we implemented two important algorithms from bioinformatics in the developed framework, namely the forward and Viterby algorithm. These algorithms typically tend to be numerically unstable, since they require computations on decreasingly small probabilities. Our implementation shows that, using the theoretical approach presented in this dissertation, it is in fact possible to efficiently solve these real world problems in the encrypted domain.English
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: Fachbereich Informatik > Krytpgraphische Protokolle
Date Deposited: 09 Jan 2012 11:33
Last Modified: 07 Dec 2012 12:01
URN: urn:nbn:de:tuda-tuprints-28112
License: Simple publication rights for ULB
Referees: Katzenbeisser, Prof. Dr. Stefan and Jha, Prof. Somesh
Refereed: 18 November 2011
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/2811
Export:

Actions (login required)

View Item View Item