Homomorphic encryption

Abstract: The problem of constructing a secure encryption scheme that allows for computation on encrypted data was an open problem for more than 30 years. In 2009, Craig Gentry solved the problem, constructing the first fully homomorphic encryption (FHE) scheme. The challenge of constructing a homomorphic encryption scheme can be divided into three main components: 1) Constructing a decryption algorithm that is a ring homomorphism. 2) Proving CPA security. 3) Managing noise growth of evaluated ciphertexts. This thesis presents a formal mathematical background to FHE and discusses these three components. To compute on ciphertexts, the decryption algorithm needs to be homomorpic with respect to multiplication and addition operation. This means, theoretically, computing and then decrypting is equivalent to decrypting and then computing. Security is proved by reductions and hardness assumptions. The standard hardness assumptions used today is the $\operatorname{LWE}$ and $\operatorname{RLWE}$ assumptions. All existing encryption schemes are based on introducing noise when encrypting. This noise grows with each ciphertext operation and without controlling noise, decryption fails given sufficiently many operations. Gentry showed that a scheme that can evaluate its own decryption circuit can be used to reduce the noise and bootstrapped into a fully homomorphic encryption scheme.