Paper 2014/873

Bootstrapping for HElib

Shai Halevi and Victor Shoup

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. Prior to this work there were very 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 somewhat-homomorphic encryption. This implementation required extending previous 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(2^{16})$. In that setting, the recryption procedure takes under 3 minutes (at security-level $\approx 80$) on a single core, and allows a multiplicative depth-11 computation before the next recryption is needed. This report updates the results that we reported in Eurocrypt 2015 in several ways. Most importantly, it includes a much more robust method for deriving the parameters, ensuring that recryption errors only occur with negligible probability. Many aspects of this analysis are proven, and for the few well-specified heuristics that we made, we report on thorough experimentation to validate them. The procedure that we describe here is also significantly more efficient than in the previous version, incorporating many optimizations that were reported elsewhere (such as more efficient linear transformations) and adding a few new ones. Finally, our implementation now also incorporates Chen and Han's techniques from Eurocrypt 2018 for more efficient digit extraction (for some parameters), as well as for ``thin bootstrapping'' when the ciphertext is only sparsely packed.

Note: Minor clarifications

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2015
Keywords
BootstrappingHomomorphic EncryptionImplementation
Contact author(s)
shaih @ alum mit edu
History
2020-04-21: last of 4 revisions
2014-10-22: received
See all versions
Short URL
https://ia.cr/2014/873
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/873,
      author = {Shai Halevi and Victor Shoup},
      title = {Bootstrapping for HElib},
      howpublished = {Cryptology ePrint Archive, Paper 2014/873},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/873}},
      url = {https://eprint.iacr.org/2014/873}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.