Paper 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].
Metadata
- Available format(s)
- Publication info
- Published elsewhere. Full version of the corresponding Asiacrypt'10 article
- Keywords
- fully homomorphic encryptionideal latticesSSSP
- Contact author(s)
- damien stehle @ gmail com
- History
- 2010-09-09: revised
- 2010-05-25: received
- See all versions
- Short URL
- https://ia.cr/2010/299
- License
-
CC BY