Paper 2018/244

Faster Homomorphic Linear Transformations in HElib

Shai Halevi and Victor Shoup

Abstract

HElib is a software library that implements homomorphic encryption (HE), with a focus on effective use of "packed" ciphertexts. An important operation (which is used in bootstrapping, as well as in other applications) is applying a known linear map to a vector of encrypted data. In this paper, we describe several algorithmic improvements that significantly speed up this operation: in our experiments, our new algorithms were 30-75 times faster than those currently implemented in HElib for typical parameters. Our techniques also reduce the size of the large public evaluation key, often using 33%-50% less space than the previous HElib implementation. We also implemented a new tradeoff that enables a drastic reduction in size, maybe a 25x factor or more for some parameters, paying only a 2-4x factor in runtime (and giving up some parallelization opportunities).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in CRYPTO 2018
Keywords
Homomorphic encryptionImplementationLinear transformationsbootstrapping
Contact author(s)
shaih @ alum mit edu
History
2019-05-11: revised
2018-03-05: received
See all versions
Short URL
https://ia.cr/2018/244
License
Creative Commons Attribution
CC BY

BibTeX

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