Fully Homomorphic Encryption - Implementing Gentry's Fully-Homomorphic Encryption Scheme
Craig Gentry and 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 effort 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.
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.
Availability. Paper available as PDF (269 Kbyte).