Naar praktische bootstrapping in volledig homomorfe encryptie

Fully homomorphic encryption supports arbitrary computations on encrypted data without requiring intermediate decryption. Even though it enables many promising applications, its adoption remains limited due to high computational overhead compared to unencrypted computations. A major cause is the need for an expensive bootstrapping algorithm, in which a homomorphic scheme evaluates its own decryption function. This dissertation presents algorithmic and implementation improvements to the bootstrapping procedures of the encryption schemes from Brakerski-Gentry-Vaikuntanathan and Brakerski-Fan-Vercauteren. To this end, we propose some adaptations. Firstly, we study the structure of polynomial functions over the relevant domain of computation. This allows us to construct an interpolant for (a subcomponent of) the decryption function that can be efficiently evaluated. Secondly, we demonstrate how to homomorphically evaluate a class of structured linear transformations, which forms another integral part of decryption. Thirdly, we reduce the latency of bootstrapping by using a generalized version of the Brakerski-Fan-Vercauteren encoding mechanism. At the same time, our new encoding method enables computations on higher-precision numbers than what was previously possible. The above improvements result in a bootstrapping algorithm that is not only more efficient, but also much easier to use and implement. In particular, at the start of this research, bootstrapping still took tens of seconds for practically useful security levels. Our most recent implementation can bootstrap in only a single second on a central processing unit in one thread, while simultaneously offering higher throughput and using a simpler mathematical construction.