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
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]