### 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].

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
See all versions
Short URL
https://ia.cr/2010/299

CC BY

BibTeX

@misc{cryptoeprint:2010/299,
author = {Damien Stehle and Ron Steinfeld},
title = {Faster Fully Homomorphic Encryption},
howpublished = {Cryptology ePrint Archive, Paper 2010/299},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/299}},
url = {https://eprint.iacr.org/2010/299}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.