Cryptology ePrint Archive: Report 2010/299
Faster Fully Homomorphic Encryption
Damien Stehle and Ron Steinfeld
Abstract: We describe two improvements to Gentry's fully homomorphic scheme
based on ideal lattices and its analysis: we provide a more aggressive
analysis of one of the hardness assumptions (the one related to the
Sparse Subset Sum Problem) and we introduce a probabilistic decryption
algorithm that can be implemented with an algebraic circuit of low
multiplicative degree. Combined together, these improvements lead to a
faster fully homomorphic scheme, with a~$\softO(\lambda^{3.5})$ bit
complexity per elementary binary add/mult gate, where~$\lambda$ is the
security parameter. These improvements also apply to the fully
homomorphic schemes of Smart and Vercauteren [PKC'2010] and van Dijk
et al.\ [Eurocrypt'2010].
Category / Keywords: fully homomorphic encryption, ideal lattices, SSSP
Publication Info: Full version of the corresponding Asiacrypt'10 article
Date: received 19 May 2010, last revised 9 Sep 2010
Contact author: damien stehle at gmail com
Available format(s): PDF | BibTeX Citation
Version: 20100909:072910 (All versions of this report)
Short URL: ia.cr/2010/299
[ Cryptology ePrint archive ]