Academic
Publications
Implementing Gentry's Fully-Homomorphic Encryption Scheme

Implementing Gentry's Fully-Homomorphic Encryption Scheme,10.1007/978-3-642-20465-4_9,Craig Gentry,Shai Halevi

Implementing Gentry's Fully-Homomorphic Encryption Scheme   (Citations: 6)
BibTex | RIS | RefWorks Download
We describe a working implementation of a variant of Gentry's fully homomorphic encryption scheme (STOC 2009), similar to the variant used in an earlier implementation efiort by Smart and Vercauteren (PKC 2010). Smart and Vercauteren implemented the underlying \somewhat homomorphic" scheme, but were not able to implement the bootstrapping functionality that is needed to get the complete scheme to work. We show a number of optimizations that allow us to implement all aspects of the scheme, including the bootstrapping functionality. Our main optimization is a key-generation method for the underlying somewhat homomor- phic encryption, that does not require full polynomial inversion. This reduces the asymptotic complexity from ~ O(n 2:5 ) to ~ O(n 1:5 ) when working with dimension-n lattices (and practically reducing the time from many hours/days to a few seconds/minutes). Other optimizations in- clude a batching technique for encryption, a careful analysis of the degree of the decryption polynomial, and some space/time trade-ofis for the fully-homomorphic scheme. We tested our implementation with lattices of several dimensions, corresponding to several security levels. From a \toy" setting in dimension 512, to \small," \medium," and \large" settings in dimensions 2048, 8192, and 32768, respectively. The public-key size ranges in size from 70 Megabytes for the \small" setting to 2.3 Gigabytes for the \large" setting. The time to run one bootstrapping operation (on a 1-CPU 64-bit machine with large memory) ranges from 30 seconds for the \small" setting to 30 minutes for the \large" setting.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...We give some background in Section 2, and then describe our implementation of the underlying “somewhat homomorphic” encryption scheme in Sections 3 through 7. A description of our optimizations that are specific to the bootstrapping functionality appears in the full version of this report [5]...

    Craig Gentryet al. Implementing Gentry's Fully-Homomorphic Encryption Scheme

    • ...For example, Gentry and Halevi [8] have been able to implement all aspects of the scheme [7]...

    Frederik Armknechtet al. An efficient distributed privacy-preserving recommendation system

    • ...It would be interesting to relax our assumptions f = x n +1 and I =( 2) ,i n case other choices prove interesting (see the full version for I =( 2 ,x +1 )). An important question is to assess the practical impact of our results (see [26,12] for implementations of Gentry’s scheme)...

    Damien Stehléet al. Faster Fully Homomorphic Encryption

    • ...Gentry and Halevi described in [6] the first implementation of Gentry’s scheme...
    • ...The authors of [6] report that for an optimized implementation on a high-end workstation, key generation takes 2.2 hours, encryption takes 3 minutes, and ciphertext refresh takes 30 minutes...
    • ...Our second contribution is to describe an implementation of the fully homomorphic DGHV scheme under our variant, using some of the optimizations from [6]...
    • ...We use the refined analysis from [17] of the sparse subset sum problem; however we do not use the probabilistic decryption circuit from [17] because as in [6] 490 J.-S...
    • ...We obtain similar performances as the Gentry-Halevi implementation of Gentry’s scheme [6]...
    • ...More precisely we use four security levels inspired by the levels from [6] (though they may not be directly comparable due to different notions of “security bits”): “toy”, “small”, “medium” and “large”, corresponding to 42, 52, 62 and 72 bits of security respectively...
    • ...Note that as in [6] we use n = � log 2 (θ +1 ) � bits of precision, instead of n = � log 2 θ� +3 in the original scheme...
    • ...The proof of the following lemma is similar to the one in [4] (see the full version of this paper [3]), but we can handle a smaller precision n, as in [6], because in our scheme, ciphertext size does not grow in homomorphic operations...
    • ...We use four security levels inspired by the levels from [6]: “toy”, “small”, “medium” and “large”, corresponding to 42, 52, 62 and 72 bits of security respectively...
    • ...To alleviate this problem, an additional compression trick is described in [6]...

    Jean-Sébastien Coronet al. Fully Homomorphic Encryption over the Integers with Shorter Public Key...

    • ...The majority of these solutions are lacking either in generality or practicality and scalability [3]...

    Isaac Agudoet al. Cryptography Goes to the Cloud

Sort by: