TU Darmstadt / ULB / TUprints

Securely Outsourcing Computations using Homomorphic Encryption

Peter, Andreas :
Securely Outsourcing Computations using Homomorphic Encryption.
Technische Universität, Darmstadt
[Ph.D. Thesis], (2013)

[img]
Preview
Text
apeter-dissertation.pdf
Available under Creative Commons Attribution Non-commercial No Derivatives, 2.5.

Download (885kB) | Preview
Item Type: Ph.D. Thesis
Title: Securely Outsourcing Computations using Homomorphic Encryption
Language: English
Abstract:

Web-servers are a dominant medium of modern communication and thus process vast amounts of highly sensitive, private data. Social networks, online auctions, and all kinds of cloud services constitute popular examples of online services complying with this paradigm. Due to many alarming scandals regarding the misuse of private data, IT security solutions protecting this sensitive data (for example by hiding it through encryption) are indispensable. Ideally, web-servers should be able to compute on private data without seeing it - we refer to this as the "Secure Outsourcing of Computation". Most notably, the cryptographic primitive of Homomorphic Encryption (HE) enables the web-servers to process data in the encrypted domain, which thereby hides/protects all private data as it is never available in the clear. More precisely, HE is a type of encryption that allows for the computation of certain functionalities on encrypted data without knowledge of the decryption key. Depending on the HE scheme, various functionalities can be evaluated in the encrypted domain, ranging from additions or multiplications only (Group Homomorphic Encryption, GHE), to virtually any computable functionality (Fully Homomorphic Encryption, FHE).

We provide a clean foundational framework for HE that permits security characterizations for a large class of HE schemes and shows strong similarities between GHE and FHE. We study these characterizations in order to assess the limits of HE, and show that GHE is obsolete in the quantum world, meaning that any GHE scheme can be broken by a quantum computer. Together with our newly constructed universal blueprint that encompasses virtually any GHE scheme, we know exactly how these schemes must be designed and what the underlying hardness assumptions must look like. To some extent, this rounds off the topic of GHE both in the standard and quantum model of computation.

In the standard model (which is presently assumed to be the most realistic model of computation), GHE is still highly attractive as it provides very efficient solutions to a variety of practical problems. On the basis of our foundational framework, we construct new GHE schemes with unique features and show their employability in practical applications. Most importantly, we use the special features of one of these schemes and develop a novel technique to achieve a practically efficient solution to the problem of securely outsourcing computations. Our construction allows multiple users to send encryptions of their private data under their own keys to a distrusted web-server that can then, on behalf of the users, evaluate any dynamically chosen computable function on these inputs in the encrypted domain (even across encryptions under different public keys) without learning anything at all, and without interacting with the users.

Alternative Abstract:
Alternative AbstractLanguage
Ein überwiegender Teil des modernen Datenaustauschs geschieht heutzutage über Webserver, welche Unmengen an sensiblen, privaten Daten verarbeiten. Zu den wichtigsten Beispielen zählen Online-Dienste, wie soziale Netzwerke, Internet-Auktionen und alle möglichen Cloud-Dienste. Viele alarmierende Skandale, die den Missbrauch privater Daten betreffen, zeigen die unbedingte Notwendigkeit von Lösungen aus dem Bereich der IT-Sicherheit, welche diese sensiblen Daten schützen (zum Beispiel durch die Benutzung von Verschlüsselungsverfahren). Idealerweise sollten Webserver in der Lage sein mit privaten Daten zu rechnen, ohne diese zu sehen - wir nennen einen solchen Mechanismus eine "sichere Auslagerung von Berechnungen". In diesem Zusammenhang ist die Homomorphe Verschlüsselung (HV) einer der bedeutendsten Bausteine der IT-Sicherheit bzw. der Kryptographie. HV ist ein Verschlüsselungsmechanismus, der es ermöglicht bestimmte Berechnungen auf verschlüsselten Daten auszuführen ohne den Entschlüsselungsschlüssel zu kennen. Abhängig von dem jeweiligen HV-Verfahren können verschiedenste Funktionen ausgewertet werden, angefangen bei simplen Additionen oder Multiplikationen (Gruppen-Homomorphe Verschlüsselung, GHV) bis hin zu nahezu allen berechenbaren Funktionen (Voll-Homomorphe Verschlüsselung, VHV). In dieser Arbeit beschäftigen wir uns zunächst mit den Grundlagen von HV und geben diverse Äquivalenzbedingungen an die Sicherheit von HV-Verfahren, sowie starke Ähnlichkeiten zwischen GHV- und VHV-Verfahren an. Wir studieren diese Bedingungen im Detail, um die Grenzen von HV zu ermitteln und zeigen, dass GHV in der Quantenwelt obsolet ist, womit gemeint ist, dass jedes solche Verfahren von einem Quantumcomputer gebrochen werden kann. Zusammen mit einem von uns neu entwickelten, universellen Konstruktionsentwurf für GHV, wissen wir dann genau, wie solche Verfahren konstruiert werden müssen und, wie die zugrundeliegenden komplexitätstheoretischen Annahmen aussehen müssen. Zu einem gewissen Grad rundet dies das Thema GHV sowohl in dem Standard- als auch in dem Quantenberechnungsmodell ab. Im Standardmodell (welches heutzutage als das realistischste Berechnungsmodell angesehen wird) ist GHV immer noch höchst attraktiv, da es genutzt wird, um sehr effiziente Lösungen für eine Vielzahl von praxisrelevanten Problemen bereitzustellen. Basierend auf unserer Grundlagenforschung zu HV, können wir neue GHV-Verfahren mit einzigartigen Eigenschaften konstruieren, welche wir dann benutzen, um Probleme aus der Praxis zu lösen. Von großer Bedeutung ist in diesem Zusammenhang unsere Erstellung eines besonderen Verfahrens, welches uns erlaubt eine neue Technik vorzustellen, um das Problem des sicheren Auslagerns von Berechnungen in einer sehr effizienten Art und Weise zu lösen. Konkret erlaubt es unsere Technik mehreren Benutzern, Verschlüsselungen ihrer privaten Daten unter ihren eigenen Schlüsseln an einen nicht-vertrauenswürdigen Webserver zu schicken, welcher dann im Auftrag der Benutzer jede beliebige berechenbare Funktion auf diesen verschlüsselten Daten zu berechnen (sogar über Verschlüsselungen unter verschiedenen Schlüsseln hinweg) ohne irgendetwas Sicherheitskritisches zu lernen und ohne mit den Benutzern zu interagieren.German
Place of Publication: Darmstadt
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: 20 Department of Computer Science
Date Deposited: 02 May 2013 09:15
Last Modified: 07 May 2013 13:36
URN: urn:nbn:de:tuda-tuprints-33813
Referees: Katzenbeisser, Prof. Dr. Stefan and Armknecht, Prof. Dr. Frederik
Refereed: 22 February 2013
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/3381
Export:
Actions (login required)
View Item View Item

Downloads

Downloads per month over past year