Katholieke Universiteit Leuven
In this paper, the authors port Brakerski's fully homomorphic scheme based on the Learning With Errors (LWE) problem to the ring-LWE setting. They introduce two optimised versions of relinearisation that not only result in a smaller relinearisation key, but also faster computations. They provide a detailed, but simple analysis of the various homomorphic operations, such as multiplication, relinearisation and bootstrapping, and derive tight worst case bounds on the noise caused by these operations. The analysis of the bootstrap-ping step is greatly simplified by using a modulus switching trick.