Efficient Fully Homomorphic Encryption over the Integers

Abstract

Fully homomorphic encryption allows a worker to perform additions and multiplications on encrypted plaintext values without decryption. The first construction of a fully homomorphic scheme (FHE) based on ideal lattices was described by Gentry in 2009. Since Gentry's breakthrough result, many improvements have been made, introducing new variants, improving efficiency, and providing new features.

The most FHE schemes still have very large ciphertexts (millions of bits for a single ciphertext). This presents a considerable bottleneck in practical deployments. To improve the efficiency of FHE schemes, especially ciphertext size, we can consider the following two observations. One is to improve the ratio of plaintext and ciphertext by packing many messages in one ciphertext and the other is to reduce the size of FHE-ciphertext by combining FHE with existing public-key encryption.

In the dissertation, we study on construction of efficient FHE over the integers. First, we propose a new variant DGHV fully homomorphic encryption to extend message space. Using Chinese remainder theorem, our scheme reduces the overheads (ratio of ciphertext computation and plaintext computation) from $\tilde{O}(\lambda^4)$ to $\tilde{O}(\lambda)$. We reduce the security of our Somewhat Homomorphic Encryption scheme to a decisional version of Approximate GCD problem (DACD).

To reduce the ciphertext size, we propose a hybrid scheme that combines public key encryption (PKE) and somewhat homomorphic encryption (SHE). In this model, messages are encrypted with a PKE and computations on encrypted data are carried out using SHE or FHE after homomorphic decryption. Our approach is suitable for cloud computing environments since it has small bandwidth, low storage requirement, and supports efficient computing on encrypted data.

We also give alternative approach to reduce the FHE ciphertext size. Some of recent SHE schemes possess two properties, the public key compression and the key switching. By combining them, we propose a hybrid encryption scheme in which a block of messages is encrypted by symmetric version of the SHE and its secret key is encrypted by the (asymmetric) SHE. The ciphertext under the symmetric key encryption is compressed by using the public key compression technique and we convert the ciphertext into asymmetric encryption to enable homomorphic computations using key switching technique.