International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Faster Fully Homomorphic Encryption

Authors:
Damien Stehlé
Ron Steinfeld
Download:
URL: http://eprint.iacr.org/2010/299
Search ePrint
Search Google
Abstract: We describe two improvements to Gentry's fully homomorphic scheme based on ideal lattices and its analysis: we provide a refined 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})$ 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].
BibTeX
@misc{eprint-2010-23200,
  title={Faster Fully Homomorphic Encryption},
  booktitle={IACR Eprint archive},
  keywords={fully homomorphic encryption, ideal lattices, SSSP},
  url={http://eprint.iacr.org/2010/299},
  note={ damien.stehle@gmail.com 14749 received 19 May 2010},
  author={Damien Stehlé and Ron Steinfeld},
  year=2010
}