Learning Without Knowing: Applying Homomorphic Encryption to Machine Learning Algorithms

Abstract

In this thesis, we survey the literature focused on homomorphic encryption schemes and the application of such schemes to machine learning algorithms. After presenting some of the theory of homomorphic encryption, we explore the Paillier cryptosystem, a somewhat homomorphic encryption scheme, and the fully homomorphic encryption scheme based on the Learning with Errors (LWE) problem given in [GSW13]. Although we do not present a fully homomorphic encryption scheme formally based on lattice-based problems, we do present a reduction from a variant of the shortest vector lattice problem to LWE. As for applications of these encryption schemes to machine learning, we examine the use of these to implement fundamental machine learning algorithms such as Fisher's Linear Discriminant, Linear Regression, Principal Component Analysis, Decision Trees, and Naive Bayes Classifiers. In many instances, there are alternative implementations of the aforementioned algorithms so that they can be successfully supported by a homomorphic encryption scheme. However, sometimes, we need to make use of algorithms that approximate certain calculations (e.g. using gradient descent instead of computing a closed form solution) due to the limited operations permitted by somewhat homomorphic encryption schemes. Finally, we consider limitations of fully homomorphic encryption regarding its security, efficiency, and impact on society. Homomorphic encryption is not without its limitations, and so we also survey alternatives to homomorphic encryption such as Yao's garbled circuits and functional encryption to better understand the particular situations that best leverage homomorphic (or fully homomorphic) encryption.