Our main optimization is a key-generation method for the underlying somewhat homomorphic encryption, that does not require full polynomial inversion. This reduces the asymptotic complexity from $\tilde{O}(n^{2.5})$ to $\tilde{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 include a batching technique for encryption, a careful analysis of the degree of the decryption polynomial, and some space/time trade-offs 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.
Category / Keywords: public-key cryptography / Fully Homomorphic Encryption, Implementation Publication Info: Extended abstract in EUROCRYPT 2011, this is the full version Date: received 8 Oct 2010, last revised 4 Feb 2011 Contact author: shaih at alum mit edu Available format(s): PDF | BibTeX Citation Version: 20110204:192637 (All versions of this report) Short URL: ia.cr/2010/520 Discussion forum: Show discussion | Start new discussion