Faster fully homomorphic encryption

Damien Stehlé; Ron Steinfeld

doi:10.1007/978-3-642-17373-8_22

Faster fully homomorphic encryption

Damien Stehlé^*, Ron Steinfeld

^*Corresponding author for this work

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

210 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 language	English
Title of host publication	Advances in Cryptology, ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Editors	Masayuki Abe
Place of Publication	Berlin; Heidelberg
Publisher	Springer, Springer Nature
Pages	377-394
Number of pages	18
Volume	6477 LNCS
ISBN (Print)	3642173721, 9783642173721
DOIs	https://doi.org/10.1007/978-3-642-17373-8_22
Publication status	Published - 2010
Event	16th Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2010 - Singapore, Singapore Duration: 5 Dec 2010 → 9 Dec 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6477 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	16th Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2010
Country/Territory	Singapore
City	Singapore
Period	5/12/10 → 9/12/10

Access to Document

10.1007/978-3-642-17373-8_22

Cite this

Stehlé, D., & Steinfeld, R. (2010). Faster fully homomorphic encryption. In M. Abe (Ed.), Advances in Cryptology, ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (Vol. 6477 LNCS, pp. 377-394). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6477 LNCS). Springer, Springer Nature. https://doi.org/10.1007/978-3-642-17373-8_22

Stehlé, Damien ; Steinfeld, Ron. / Faster fully homomorphic encryption. Advances in Cryptology, ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. editor / Masayuki Abe. Vol. 6477 LNCS Berlin; Heidelberg : Springer, Springer Nature, 2010. pp. 377-394 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ffe1f0f591a34712b5e1b7764a311fd7,

title = "Faster fully homomorphic encryption",

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 {\~O}(λ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].",

author = "Damien Stehl{\'e} and Ron Steinfeld",

year = "2010",

doi = "10.1007/978-3-642-17373-8_22",

language = "English",

isbn = "3642173721",

volume = "6477 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "377--394",

editor = "Masayuki Abe",

booktitle = "Advances in Cryptology, ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

address = "United States",

note = "16th Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2010 ; Conference date: 05-12-2010 Through 09-12-2010",

}

Stehlé, D & Steinfeld, R 2010, Faster fully homomorphic encryption. in M Abe (ed.), Advances in Cryptology, ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. vol. 6477 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6477 LNCS, Springer, Springer Nature, Berlin; Heidelberg, pp. 377-394, 16th Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2010, Singapore, Singapore, 5/12/10. https://doi.org/10.1007/978-3-642-17373-8_22

Faster fully homomorphic encryption. / Stehlé, Damien; Steinfeld, Ron.
Advances in Cryptology, ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. ed. / Masayuki Abe. Vol. 6477 LNCS Berlin; Heidelberg: Springer, Springer Nature, 2010. p. 377-394 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6477 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Faster fully homomorphic encryption

AU - Stehlé, Damien

AU - Steinfeld, Ron

PY - 2010

Y1 - 2010

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

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

UR - http://www.scopus.com/inward/record.url?scp=78650833995&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17373-8_22

DO - 10.1007/978-3-642-17373-8_22

M3 - Conference proceeding contribution

AN - SCOPUS:78650833995

SN - 3642173721

SN - 9783642173721

VL - 6477 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 377

EP - 394

BT - Advances in Cryptology, ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

A2 - Abe, Masayuki

PB - Springer, Springer Nature

CY - Berlin; Heidelberg

T2 - 16th Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2010

Y2 - 5 December 2010 through 9 December 2010

ER -

Stehlé D, Steinfeld R. Faster fully homomorphic encryption. In Abe M, editor, Advances in Cryptology, ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Vol. 6477 LNCS. Berlin; Heidelberg: Springer, Springer Nature. 2010. p. 377-394. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-17373-8_22

Faster fully homomorphic encryption

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this