XZDDF Bootstrapping in Fully Homomorphic Encryption

Abstract: Despite the vast research on the topic in recent years, fully homomorphic encryption schemes remain time-inefficient. The main bottleneck is the so-called bootstrapping, whose purpose is to reduce noise that has accumulated after having performed homomorphic operations on a ciphertext. This thesis is about bootstrapping, and how to do it more efficiently. More specifically, a new algorithm, here called XZDDF, is analyzed. The thesis contains a solution to a problem in the original XZDDF algorithm that was encountered during the project. The new algorithm was then implemented in the open-source library OpenFHE. Theoretically, the algorithm has lower time complexity than previous bootstrapping techniques, but the execution time of the implementation was not faster than other algorithms.