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