Faster fully homomorphic encryption

Damien Stehlé*, Ron Steinfeld

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

170 Citations (Scopus)

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 Õ(λ3.5) bit complexity per elementary binary add/mult gate, where λ 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].

Original languageEnglish
Title of host publicationAdvances in Cryptology, ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
EditorsMasayuki Abe
Place of PublicationBerlin; Heidelberg
PublisherSpringer, Springer Nature
Pages377-394
Number of pages18
Volume6477 LNCS
ISBN (Print)3642173721, 9783642173721
DOIs
Publication statusPublished - 2010
Event16th Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2010 - Singapore, Singapore
Duration: 5 Dec 20109 Dec 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6477 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other16th Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2010
CountrySingapore
CitySingapore
Period5/12/109/12/10

Fingerprint Dive into the research topics of 'Faster fully homomorphic encryption'. Together they form a unique fingerprint.

Cite this