Bootstrapping for HElib

Shai Halevi, Victor Shoup

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

Abstract

Gentry’s bootstrapping technique is still the only known method of obtaining fully homomorphic encryption where the system’s parameters do not depend on the complexity of the evaluated functions. Bootstrapping involves a recryption procedure where the scheme’s decryption algorithm is evaluated homomorphically. So far, there have been precious few implementations of recryption, and fewer still that can handle “packed ciphertexts” that encrypt vectors of elements. In the current work, we report on an implementation of recryption of fully-packed ciphertexts using the HElib library for somewhathomomorphic encryption. This implementation required extending the recryption algorithms from the literature, as well as many aspects of the HElib library. Our implementation supports bootstrapping of packed ciphertexts over many extension fields/rings. One example that we tested involves ciphertexts that encrypt vectors of 1024 elements from GF(216). In that setting, the recryption procedure takes under 5.5 minutes (at security-level ≈ 76) on a single core, and allows a depth-9 computation before the next recryption is needed.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsMarc Fischlin, Elisabeth Oswald
PublisherSpringer Verlag
Pages641-670
Number of pages30
ISBN (Print)9783662467992
DOIs
StatePublished - 2015
Event34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2015 - Sofia, Bulgaria
Duration: Apr 26 2015Apr 30 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9056
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2015
CountryBulgaria
CitySofia
Period4/26/154/30/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Bootstrapping for HElib'. Together they form a unique fingerprint.

  • Cite this

    Halevi, S., & Shoup, V. (2015). Bootstrapping for HElib. In M. Fischlin, & E. Oswald (Eds.), Advances in Cryptology – EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 641-670). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9056). Springer Verlag. https://doi.org/10.1007/978-3-662-46800-5_25