Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
General Methods
Homomorphic Encryption
Public Key
Space Time
Subscribe
Academic
Publications
Implementing Gentry's FullyHomomorphic Encryption Scheme
Implementing Gentry's FullyHomomorphic Encryption Scheme,10.1007/9783642204654_9,Craig Gentry,Shai Halevi
Edit
Implementing Gentry's FullyHomomorphic Encryption Scheme
(
Citations: 6
)
BibTex

RIS

RefWorks
Download
Craig Gentry
,
Shai Halevi
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 keygeneration 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 dimensionn 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 tradeofis for the fullyhomomorphic 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 publickey 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 1CPU 64bit machine with large memory) ranges from 30 seconds for the \small" setting to 30 minutes for the \large" setting.
Conference:
Theory and Application of Cryptographic Techniques  EUROCRYPT
, pp. 129148, 2011
DOI:
10.1007/9783642204654_9
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
eprint.iacr.org
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
More »
Citation Context
(6)
...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 Gentry
,
et al.
Implementing Gentry's FullyHomomorphic Encryption Scheme
...For example, Gentry and Halevi [
8
] have been able to implement all aspects of the scheme [7]...
Frederik Armknecht
,
et al.
An efficient distributed privacypreserving 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 highend 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 GentryHalevi 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
]...
JeanSébastien Coron
,
et 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 Agudo
,
et al.
Cryptography Goes to the Cloud
References
(15)
Predicting Lattice Reduction
(
Citations: 44
)
Nicolas Gama
,
Phong Q. Nguyen
Conference:
Theory and Application of Cryptographic Techniques  EUROCRYPT
, pp. 3151, 2008
Fully homomorphic encryption using ideal lattices
(
Citations: 125
)
Craig Gentry
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 169178, 2009
Toward Basing Fully Homomorphic Encryption on WorstCase Hardness
(
Citations: 7
)
Craig Gentry
Conference:
International Crytology Conference  CRYPTO
, pp. 116137, 2010
PublicKey Cryptosystems from Lattice Reduction Problems
(
Citations: 150
)
Oded Goldreich
,
Shafi Goldwasser
,
Shai Halevi
Conference:
International Crytology Conference  CRYPTO
, pp. 112131, 1997
On Ideal Lattices and Learning with Errors over Rings
(
Citations: 11
)
Vadim Lyubashevsky
,
Chris Peikert
,
Oded Regev
Conference:
Theory and Application of Cryptographic Techniques  EUROCRYPT
, pp. 123, 2010
Sort by:
Citations
(6)
Implementing Gentry's FullyHomomorphic Encryption Scheme
(
Citations: 6
)
Craig Gentry
,
Shai Halevi
Conference:
Theory and Application of Cryptographic Techniques  EUROCRYPT
, pp. 129148, 2011
An efficient distributed privacypreserving recommendation system
Frederik Armknecht
,
Thorsten Strufe
Conference:
The IFIP Annual Mediterranean Ad Hoc Networking Workshop  MedHocNet
, 2011
Faster Fully Homomorphic Encryption
(
Citations: 6
)
Damien Stehlé
,
Ron Steinfeld
Published in 2010.
Fully Homomorphic Encryption over the Integers with Shorter Public Keys
(
Citations: 2
)
JeanSébastien Coron
,
Avradip Mandal
,
David Naccache
,
Mehdi Tibouchi
Cryptography Goes to the Cloud
Isaac Agudo
,
David Nuñez
,
Gabriele Giammatteo
,
Panagiotis Rizomiliotis
,
Costas Lambrinoudakis