Cryptology ePrint Archive: Report 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.

Category / Keywords:

Original Publication (with minor differences): IACR-EUROCRYPT-2015

Date: received 29 Aug 2016, last revised 4 Sep 2016

Contact author: damien stehle at gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20160904:211209 (All versions of this report)

Short URL: ia.cr/2016/837