A Summary of the FV Homomorphic Encryption Scheme and the Average-Case Noise Growth

Abstract

Homomorphic encryption is a method of encryption that allows for secure computation of data. Many industries are moving away from owning expensive high-powered computers and instead delegating costly computations to the cloud. In an age of data breaches, there is an inherent risk when putting sensitive data on the cloud. Homomorphic encryption allows one to securely perform computations on the cloud without allowing the host or any other party access to the raw data itself. One application being explored is encrypting health data on low-powered embedded devices, uploading it to a cloud application, performing computations to assess health risks, and send the results back to the user’s device for decryption and interpretation. Another application being explored is digital voting. This thesis aims to provide a summary of the current state-of-the-art of homomorphic encryption. We will begin by providing the reader with sources for the current main im- plementations and schemes they are based on. We will then present the mathematical background used in existing schemes. This includes a background on lattices, cyclotomic fields, rings of integers, and the underlying believed-to-be-hard problems existing schemes take advantage of. We will then shift our attention to the FV scheme which is based on the ring-LWE problem and is one of the main schemes used today. We will then briefly discuss some optimizations used in FV implementations. Finally, we will look at some probabilistic experiments which suggest the noise growth in FV is significantly lower than the theoretical maximum in the average case, and will explore some of the benefits that can be gained.