Fully Homomophic Encryption over the Integers Revisited
Jung Hee Cheon and Damien Stehlé
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.
Download: pdf.
Homepage