Fully Homomorphic Encryption over the Integers with Shorter Public Keys

By Jean-Sébastien Coron, Avradip Mandal, David Naccache, Mehdi Tibouchi. IACR Cryptology ePrint Archive, 2011

487 citations recorded by the source corpus.

At Eurocrypt 2010 van Dijk et al. described a fully homomorphic encryption scheme over the integers. The main appeal of this scheme (compared to Gentry's) is its conceptual simplicity. This simplicity comes at the expense of a public key size in O(λ10) which is too large for any practical system. In this paper we reduce the public key size to O(λ7) by encrypting with a quadratic form in the public key elements, instead of a linear form. We prove that the scheme remains semantically secure, based on a stronger variant of the approximate-GCD problem, already considered by van Dijk et al. We alsodescribe the first implementation of the resulting fully homomorphic scheme. Borrowing some optimizations from the recent Gentry-Halevi implementation of Gentry's scheme, we obtain roughly the same level of efficiency. This shows that fully homomorphic encryption can be implemented using simple arithmetic operations.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/bc48aa6ea7f3e2095b305528389e0a5009ef52ab

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Cryptanalysis of a homomorphic encryption scheme from ISIT 2008 (2012, background): “After that, further research focused on how to fast implement the existing fully homomorphic schemes [29], [14], and how to construct new homomorphic encryption schemes based on other hard problems, such as approximate greatest common divisor problems [8], [6] and Ring-LWE [2], [3].”
Somewhat Practical Fully Homomorphic Encryption (2012, methodology): “The first variants [21, 18, 20, 4, 5] of Gentry’s scheme all followed the same structure and as such had to make additional security assumptions to enable the squashing step.”
Homomorphic Evaluation of the AES Circuit (2012, background): “Some of these works were accompanied by implementation [19,10,6,20,14,7], but all the implementations so far were either “proofs of concept” that can compute only one basic operation at a time (at great cost), or special-purpose implementations limited to evaluating very simple functions.”
Homomorphic Encryption (2017, background): “The first generation of FHE constructions included the schemes from [38, 89] and some variations [86, 41, 27, 40].”
High-Speed Fully Homomorphic Encryption Over the Integers (2014, methodology): “The encryption primitive of the scheme [9], denoted by CMNT here, is implemented in this paper.”
Accelerating LTV Based Homomorphic Encryption in Reconfigurable Hardware (2015, methodology): “[10,11] were designed and implemented on a Xilinx Virtex-7 FPGA.”
Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme (2013, background): “Gentry’s scheme effectively laid down a blueprint for constructing FHE schemes and paved the way for many further constructions [26,2,3,5,4,23,19,10,8].”
A Survey on Homomorphic Encryption Schemes (2017, methodology): “ et al. in a different work [Coron et al. 2012] improved public key size to 10 MB, key generation to 10 minutes, and recryption procedure to 11 min 34 seconds using the similar parameter settings in [Coron et al. 2011]. This performance is obtained using a compression technique on the public key. In”
Accelerating integer-based fully homomorphic encryption using Comba multiplication (2014, methodology): “Another type of FHE scheme is the proposed FHE over the integers, introduced by van Dijk et al. [7] and extended by Coron et al. [11], [12].”
(Leveled) fully homomorphic encryption without bootstrapping (2012, unknown): “construction based on ideal lattices [8], there are by now a number of such schemes in the literature [6, 20, 10, 5, 4, 13], all of which are based on lattices (either directly or implicitly).”
SHIELD: Scalable Homomorphic Implementation of Encrypted Data-Classifiers (2015, unknown): “F”