TU Darmstadt / ULB / TUprints

Information-Theoretic Privacy in Verifiable Outsourced Computation

Schabhüser, Lucas (2019):
Information-Theoretic Privacy in Verifiable Outsourced Computation.
Darmstadt, Technische Universität,
[Ph.D. Thesis]

[img]
Preview
Text
schabhueser_information_theoretic_privacy_in_vc.pdf - Accepted Version
Available under CC-BY-NC-ND 4.0 International - Creative Commons, Attribution Non-commerical, No-derivatives.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Title: Information-Theoretic Privacy in Verifiable Outsourced Computation
Language: English
Abstract:

Today, it is common practice to outsource time-consuming computations to the cloud. Using the cloud allows anyone to process large quantities of data without having to invest in the necessary hardware, significantly lowering cost requirements. In this thesis we will consider the following work flow for outsourced computations: A data owner uploads data to a server. The server then computes some function on the data and sends the result to a third entity, which we call verifier.

In this scenario, two fundamental security challenges arise. A malicious server may not perform the computation correctly, leading to an incorrect result. Verifiability allows for the detection of such results. In order for this to be practical, the verification procedure needs to be efficient. The other major challenge is privacy. If sensitive data, for example medical data is processed it is important to prevent unauthorized access to such sensitive information. Particularly sensitive data has to be kept confidential even in the long term.

The field of verifiable computing provides solutions for the first challenge. In this scenario, the verifier can check that the result that was given was computed correctly. However, simultaneously addressing privacy leads to new challenges. In the scenario of outsourced computation, privacy comes in different flavors. One is privacy with respect to the server, where the goal is to prevent the server from learning about the data processed. The other is privacy with respect to the verifier. Without using verifiable computation the verifier obviously has less information about the original data than the data owner - it only knows the output of the computation but not the input to the computation. If this third party verifier however, is given additional cryptographic data to verify the result of the computation, it might use this additional information to learn information about the inputs. To prevent that a different privacy property we call privacy with respect to the verifier is required. Finally, particularly sensitive data has to be kept confidential even in the long term, when computational privacy is not suitable any more. Thus, information-theoretic measures are required. These measures offer protection even against computationally unbounded adversaries.

Two well-known approaches to these challenges are homomorphic commitments and homomorphic authenticators. Homomorphic commitments can provide even information-theoretic privacy, thus addressing long-term security, but verification is computationally expensive. Homomorphic authenticators on the other hand can provide efficient verification, but do not provide information-theoretic privacy.

This thesis provides solutions to these research challenges -- efficient verifiability, input-output privacy and in particular information-theoretic privacy.

We introduce a new classification for privacy properties in verifiable computing. We propose function-dependent commitment, a novel framework which combines the advantages of homomorphic commitments and authenticators with respect to verifiability and privacy. We present several novel homomorphic signature schemes that can be used to solve verifiability and already address privacy with respect to the verifier. In particular we construct one such scheme fine-tailored towards multivariate polynomials of degree two as well as another fine-tailored towards linear functions over multi-sourced data. The latter solution provides efficient verifiability even for computations over data authenticated by different cryptographic keys. Furthermore, we provide transformations for homomorphic signatures that add privacy. We first show how to add computational privacy and later on even information-theoretic privacy. In this way, we turn homomorphic signatures into function-dependent commitments. By applying this transformation to our homomorphic signature schemes we construct verifiable computing schemes with information-theoretic privacy.

Alternative Abstract:
Alternative AbstractLanguage
Heutzutage ist es üblich aufwendige Berechnungen in der Cloud durchzuführen. Das Nutzen der Cloud erlaubt es jedem große Mengen an Daten zu verarbeiten ohne selbst in die dafür notwendige Hardware investieren zu müssen. Dies führt zu signifikanten Kosteneinsparungen. In dieser Thesis betrachten wir den folgenden Arbeitsablauf für ausgelagerte Berechnungen: Ein Dateneigner lädt seien Daten hoch auf einen Server. Der Server berechnet dann eine Funktion über diesen Daten und sendet das Ergebnis zu einer dritten Partei, welche wir Verifizierer nennen. In diesem Szenario gibt es zwei fundamentale Sicherheitsprobleme. Ein bösartiger Server kann von der vorgeschriebenen Berechnung abweichen und so ein inkorrektes Ergebnis weitergeben. Effiziente Verifizierbarkeit erlaubt es solche Ergebnisse zu erkennen. Das andere große Sicherheitsproblem ist Vertraulichkeit. Wenn sensible Daten, zum Beispiel Gesundheitsdaten verarbeitet werden, muss sichergestellt werden, dass diese nicht in falsche Hände geraten. Für besonders sensible Daten muss dies sogar langfristig sichergestellt werden. So genanntes Verifiable Computing erlaubt es das erste Problem zu lösen. In diesem Szenario kann der Verifizierer überprüfen ob ein Ergebnis korrekt berechnet wurde. Möchte man zusätzlich Vertraulichkeit gewährleisten, so ergeben sich neue Herausforderungen. Im Szenario von Verifiable Computing sind verschiedene Varianten von Vertraulichkeit zu beachten. Eine ist Vertraulichkeit dem Server gegenüber. Hier geht es darum zu verhindern, dass der Server Informationen über die Daten erhält, welche er verarbeitet. Die andere ist Vertraulichkeit dem Verifizierer gegenüber. Ohne Verifiable Computing hat der Verifizierer offensichtlich weniger Informationen über die Daten als der Dateneigner. Er kennt lediglich das Ergebnis einer Berechnung, nicht aber die Eingabewerte. Wenn ein solcher Verifizierer aber zusätzliche kryptographische Daten erhält um die Korrektheit des Ergebnis zu überprüfen, so kann er versuchen über diese Informationen über die Eingaben abzuleiten. Weiterhin ist es für besonders sensible Daten wichtig, die Vertraulichkeit langfristig zu garantieren. Hierfür reichen Maßnahmen, die auf Annahmen über beschränkte Rechenpower beruhen nicht mehr aus und informationstheoretische Ansätze werden benötigt. Diese erlauben sogar Schutz vor Angreifern welche über unbeschränkte Rechenpower verfügen. Zwei bekannte kryptographische Lösungsansätze für diese Probleme sind homomorphe Commitment Verfahren und homomorphe Authentikatoren. Homomorphe Commitment Verfahren erlauben sogar informations-theoretisch vertrauliche Verifizierbarkeit, aber die Verifizierung ist extrem aufwendig. Homomorphe Authentikatoren können andererseits effiziente Verifizierung ermöglichen, erlauben aber keine informationstheoretische Vertraulichkeit, In dieser Arbeit entwickeln wir Lösungen für diese Herausforderungen -- effiziente Verifizierbarkeit, Vertraulichkeit für Eingaben und Ausgaben insbesodnere informationstehoretische Vertraulichkeit. Wir beschreiben zunächst eine neue Klassifizierung für die verschiedenen Vertraulichkeitsaspekte im Verifiable Computing. Dann präsentieren wir "Function-Dependent Commitment" Verfahren, welche die Vorteile von homomorphen Authentikatoren und Commitment Verfahren vereinen. Wir zeigen weiterhin, wie man homomorphe Authentikatoren transformieren kann um zusätzliche Vertaulichkeitsgarantien zu erhalten. Auf diese Art können wir homomorphe Authentikatoren in "Function-Dependent Commitment" Verfahren überführen. Indem wir dies auf die in dieser Arbeit entwickelten homomorphen Authentikatoren anwenden erhalten wir Verifiable Computing Verfahren mit informationshteoretischer Vertraulichkeit.German
Place of Publication: Darmstadt
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: 20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
Date Deposited: 27 Sep 2019 10:41
Last Modified: 27 Sep 2019 10:41
URN: urn:nbn:de:tuda-tuprints-90529
Referees: Buchmann, Prof. Dr. Johannes and Ryan, Prof. Dr. Peter
Refereed: 24 April 2019
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/9052
Export:
Actions (login required)
View Item View Item