Parameter Constraints on Homomorphic Encryption Over the Integers

Abstract

The research paper Fully Homomorphic Encryption over the Integers by van Dijk, Gentry, Halevi, and Vaikuntanathan [31] explores the construction of an encryption scheme over the integers that is fully homomorphic, using modular arithmetic. The plaintext messages in this encryption are single bits and the ciphertexts are large integers. The homomorphic property means that the algebraic operations on the plaintexts can be carried out analogously on the ciphertexts. We analyze in detail the parameter constraints required to make the scheme functional and secure, prove auxiliary results about noise accumulation, and generate a toy example to concretely illustrate parts of the scheme.