Machine learning on encrypted data

Wiesberg, Angela

Vorschau

PDF
Final_Version.pdf - Veröffentlichte Version
Download (1MB)

URL:	https://madoc.bib.uni-mannheim.de/46375
URN:	urn:nbn:de:bsz:180-madoc-463753
Dokumenttyp:	Dissertation
Erscheinungsjahr:	2018
Ort der Veröffentlichung:	Mannheim
Hochschule:	Universität Mannheim
Gutachter:	Armknecht, Frederik
Datum der mündl. Prüfung:	31 August 2018
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Practical Computer Science IV: Dependable Systems Engineering (Armknecht 2015-)
Fachgebiet:	004 Informatik
Normierte Schlagwörter (SWD):	Maschinelles Lernen , Quellencodierung , Chiffrierung
Freie Schlagwörter (Englisch):	Machine Learning , Encoding , Fully Homomorphic Encryption
Abstract:	In a time in which computing power has never been cheaper and the possibilities of extracting knowledge from data seem ever-increasing, the idea of doing this while protecting the user's privacy seems too good to be true. However, with the introduction of the first Fully Homomorphic Encryption scheme in 2009, we now have at our disposal a whole collection of encryption schemes that allow arbitrary computations on encrypted data. With this primitive, a user can encrypt his data, send it somewhere to be analyzed, and obtain the encrypted result - all without divulging anything about the data to the computing party. This is especially useful in the context of Machine Learning: A service provider can have a model that returns predictions on input data, and a user can obtain these predictions on his data without having to share it with the service provider. This is particularly important because this data is often of a sensitive nature, e.g. in medical or financial contexts. While Fully Homomorphic Encryption schemes solve this problem on a high level, there are some challenges in practice. A prominent one is the issue of encoding: Real-world data usually consists of rational numbers, whereas the plaintext space of Fully Homomorphic Encryption schemes is generally a finite field. Thus, we need an efficient way to encode the data into these plaintext spaces, and a guideline which of the finite fields to choose in the first place. Since Fully Homomorphic Encryption schemes are still very slow computationally, this choice has a huge impact on the performance. The efficiency of different encoding choices is measured with three metrics: The number of additions we need to perform in the underlying plaintext space for a given computation on the rational numbers, the number of multiplications in the plaintext space, and the multiplicative depth. The latter measures the number of consecutive multiplications in the plaintext space needed to perform a computation on rational numbers, and is motivated by the concrete structure of the Fully Homomorphic Encryption schemes we have today. In this work, we first show in Chapter 2 that among all finite fields GF(p^k), when adding or multiplying two natural numbers, the choice GF(2) is best in terms of the number of additions and multiplications. In terms of multiplicative depth there is no generic optimum, as this depends on the concrete function and the input length of the function arguments. However, we do show that choosing k>1 always has worse performance than choosing GF(p). Because of this finding, we focus on the encoding base GF(2) in the rest of the work. In Chapter 3, we extend our analysis to include negative numbers, and thus examine the effort incurred by the two most popular encoding for signed numbers, Two's Complement and Sign-Magnitude. We see that Two's Complementis better for adding, and Sign-Magnitude is better for multiplying two numbers. We utilize this fact to invent a new encoding, called Hybrid Encoding, which essentially switches between the two to minimize the effort. Our new encoding induces a performance gain of over 70% in some of our applications. We then extend our analysis from integer to rational numbers in Chapter 4. We propose several optimizations, which result in an efficiency gain of over 95%. We also propose ways to speed up the comparison function, and to reduce bitlengths in computations where some assumptions are met. The latter reduces the runtime by over 76% in our computations. In Chapter 5, we apply our findings to algorithms from Machine Learning: We perform a classification using the Linear Means Classifier, and see the large impact that our Hybrid Encoding has. We then tackle the more complicated task of training a Machine Learning algorithm on encrypted data. We use the Perceptron for this, and see that our length management procedure can decrease runtimes enormously. We also again see that the Hybrid Encoding vastly outperforms the other two encodings. Lastly, we move to the clustering problem from the area of unsupervised learning, where we run the K-Means-Algorithm on encrypted data. We adapt the algorithm to make it efficiently executable in the Fully Homomorphic Encryption context, and show that the performance of this new algorithm is similar to that of the original K-Means-Algorithm in terms of clustering accuracy. The runtime is reduced by more than 95% compared to straightforward approaches of executing the K-Means-Algorithm on encrypted data. We thus see that we can indeed perform algorithms from the world of Machine Learning on encrypted data, and that by choosing the encoding wisely and employing optimizations where we can, we can significantly speed up computations. We also see that modifying an algorithm to make it executable on encrypted data at all can yield results comparable to the original algorithm, and is thus a promising way to extend the class of algorithms we can evaluate on encrypted data. This work is based on the publications [ABC+15], [JA16], [JA17] and [JA18].
Übersetzter Titel:	Maschinelles Lernen auf verschüsselten Daten (Deutsch)
Übersetzung des Abstracts:	Wir leben in einer Zeit, in der Rechenleistung nie günstiger war und die Möglichkeiten, Wissen aus Daten zu gewinnen, stetig zunehmen. Die Idee, dies ohne Einschränkung der Privatsphäre des Nutzers zu tun, klingt hier fast zu gut, um wahr zu sein. Nach der Entdeckung des ersten vollhomomorphen Verschlüsselungsverfahrens im Jahr 2009 stehen uns allerdings inzwischen eine ganze Reihe von Verschlüsselungsverfahren zur Verfügung, die sogar beliebige Berechnungen auf verschlüsselten Daten erlauben. Mit diesem Ansatz kann ein Nutzer seine Daten verschlüsseln und versenden, um sie von einem Anbieter analysieren zu lassen, und erhält das verschlüsselte Resultat dieser Analyse zurück - alles, ohne dem Anbieter den Inhalt der Daten offenzulegen. Dies ist besonders im Kontext des maschinellen Lernens nützlich: Ein Service-Anbieter kann so über ein Modell verfügen, welches aus Eingabedaten Vorhersagen berechnet, und der Nutzer kann diese Vorhersagen für seine Daten erhalten, ohne selbige dem Anbieter offenlegen zu müssen. Dies ist vor allem dann wichtig, wenn die Daten sensibel sind, z.B. im medizinischen oder Finanz-Bereich. Während vollhomomorphe Verschlüsselungsverfahren dieses Problem im Prinzip lösen, gibt es in der Praxis einige Hindernisse zu überwinden. Ein besonders wichtiger Aspekt ist hier die Kodierung: Die Daten bestehen meist aus rationalen Zahlen, wohingegen die Nachrichtenräume der vollhomomorphen Verschlüsselungsverfahren endliche Körper sind. Man benötigt also einen möglichst effizienten Weg, um die Daten in den Nachrichtenräumen zu kodieren. Ferner benötigt man eine Richtlinie, welchen endlichen Körper man überhaupt als Nachrichtenraum wählen sollte. Da vollhomomorphe Verschlüsselungsverfahren noch sehr langsam in ihren Berechnungen sind, hat diese Wahl einen enormen Einfluss auf ihre Performanz. Die Effizienz der verschiedenen Wahlmöglichkeiten der Kodierung wird anhand von drei Metriken gemessen: Erstens die Anzahl der Additionen, die im zugrundeliegenden Nachrichtenraum ausgeführt werden müssen, um eine gegebene Berechnung auf den rationalen Daten auszuführen. Zweitens die Anzahl der Multiplikationen im Nachrichtenraum, und drittens die multiplikative Tiefe. Letztere misst, wie viele aufeinanderfolgende Multiplikationen man im Nachrichtenraum ausführen muss, um eine Berechnung auf den rationalen Daten durchzuführen, und ist in der konkreten Struktur der heutigen vollhomomorphen Verschlüsselungsverfahren begründet. In dieser Arbeit zeigen wir zunächst in Kapitel 2, dass die Addition oder Multiplikation zweier rationalen Zahlen am besten im endlichen Körper GF(2) geschehen sollte, wenn man die Anzahl der Additionen oder Multiplikationen im Nachrichtenraum als Metrik betrachtet. Wählt man die mutliplikative Tiefe als Metrik, so existiert kein generisches Optimum, da die geringste Tiefe von der konkreten Funktion, die berechnet werden soll, und der Länge der Eingaben dieser Funktion abhängt. Wir zeigen jedoch, dass die Wahl k>1 für die endlichen Körper GF(p^k) niemals von Vorteil ist, und man stattdessen stets mit endlichen Körpern der Form GF(p) arbeiten sollte. Aufgrund dieser Resultate beschränken wir uns im Rest dieser Arbeit auf den Nachrichtenraum GF(2). In Kapitel 3 erweitern wir unsere Analyse auf negative Zahlen und vergleichen zu diesem Zweck die Kosten für die zwei beliebtesten Kodierungen für ganze Zahlen, Two's Complement und Sign-Magnitude. Wir stellen fest, dass Two's Complement besser ist, um zwei Zahlen zu addieren, und dass Sign-Magnitude besser ist, um sie zu multiplizieren. Wir nutzen diese Tatsache, um eine neue Kodierung zu entwickeln, welche wir Hybrid Encoding nennen. Sie wechselt im Wesentlichen zwischen Two's Complement und Sign-Magnitude, um die Kosten zu minimieren. Unsere neue Kodierung reduziert für einige unserer Anwendungen die Laufzeit um mehr als 70%. Wir erweitern anschließend in Kapitel 4 unsere Analyse von den ganzen auf die rationalen Zahlen. Wir stellen verschiedene Optimierungen vor, welche die Effizienz um mehr als 95% steigern. Wir zeigen außerdem, wie man den Vergleich von zwei verschlüsselten Zahlen beschleunigen kann und wie man die Bitlänge unter bestimmten Annahmen verkleinern kann. Letzteres reduziert die Laufzeit unserer Berechnungen um über 76%. Schließlich wenden wir in Kapitel 5 unsere Erkenntnisse auf Algorithmen aus dem Bereich des maschinellen Lernens an: Wir führen zunächst eine Klassifizierung mit dem Linear Means Classifier durch und sehen, welch großen Einfluss unser Hybrid Encoding hierbei hat. Anschließend nehmen wir uns die kompliziertere Aufgabe vor, ein Modell auf verschlüsselten Daten zu trainieren. Wir verwenden hierzu das Perceptron und stellen fest, dass unsere Reduzierung der Bitlängen die Laufzeit enorm verkürzen kann. Wir sehen zudem auch hier wieder, dass unser Hybrid Encoding deutlich schneller als die anderen beiden Kodierungen ist. Schließlich wenden wir uns dem Clustering-Problem aus dem Gebiet des unüberwachten Lernens zu und implementieren den K-Means-Algorithmus auf verschlüsselten Daten. Wir adaptieren den Algorithmus, um ihn im Kontext der vollhomomorphen Verschlüsselung effizient ausführbar zu machen, und zeigen, dass die Genauigkeit des neuen Algorithmus vergleichbar mit der des ursprünglichen K-Means-Algorithmus ist. Die Laufzeit wird hierdurch um mehr als 95% reduziert im Vergleich zu trivialen Ansätzen, den K-Means-Algorithmus auf verschlüsselten Daten auszuführen. Wir schließen also, dass wir Algorithmen aus dem Bereich des maschinellen Lernens in der Tat auf verschlüsselten Daten ausführen und so die Privatsphäre des Nutzers schützen können. Außerdem sehen wir, dass eine geschickte Wahl der Kodierung und die Anwendung verschiedener Optimierungen die Effizienz erheblich verbessern. Wir stellen auch fest, dass die Modifizierung eines bestehenden Algorithmus mit dem Ziel, ihn auf verschlüsselten Daten ausführbar zu machen, zu einer mit dem ursprünglichen Algorithmus vergleichbaren Genauigkeit führen kann. Somit können wir die Klasse derjenigen Algorithmen, welche wir auf verschlüsselten Daten ausführen können, erheblich erweitern. Diese Arbeit basiert auf den Veröffentlichungen [ABC+15], [JA16], [JA17] und [JA18]. (Deutsch)
Zusätzliche Informationen:	Geburtsname: Jäschke, Angela