Machine learning on encrypted data

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]