Paper 2016/837

Fully Homomorphic Encryption over the Integers Revisited

Jung Hee Cheon and Damien Stehle

Abstract

Two main computational problems serve as security foundations of current fully homomorphic encryption schemes: Regev's Learning With Errors problem (LWE) and Howgrave-Graham's Approximate Greatest Common Divisor problem (AGCD). Our first contribution is a reduction from LWE to AGCD. As a second contribution, we describe a new AGCD-based fully homomorphic encryption scheme, which outperforms all prior AGCD-based proposals: its security does not rely on the presumed hardness of the so-called Sparse Subset Sum problem, and the bit-length of a ciphertext is only softO(lambda), where lambda refers to the security parameter.

Note: Updated the Eurocrypt 2015 version, to fix a few minor errors.