Faster homomorphic linear transformations in HElib

Shai Halevi, Victor Shoup

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

Abstract

HElib is a software library that implements homomorphic encryption (HE), with a focus on effective use of “packed” ciphertexts. An important operation 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 are 30–75 times faster than those previously implemented in HElib for typical parameters. One application that can benefit from faster linear transformations is bootstrapping (in particular, “thin bootstrapping” as described in [Chen and Han, Eurocrypt 2018]). In some settings, our new algorithms for linear transformations result in a 6 × speedup for the entire thin bootstrapping operation. 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, resulting in a 25 × factor or more for some parameters, paying only a penalty of a 2– 4 × times slowdown in running time (and giving up some parallelization opportunities).

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2018 - 38th Annual International Cryptology Conference, 2018, Proceedings
EditorsAlexandra Boldyreva, Hovav Shacham
PublisherSpringer Verlag
Pages93-120
Number of pages28
ISBN (Print)9783319968834
DOIs
StatePublished - 2018
Event38th Annual International Cryptology Conference, CRYPTO 2018 - Santa Barbara, United States
Duration: Aug 19 2018Aug 23 2018

Publication series

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

Other

Other38th Annual International Cryptology Conference, CRYPTO 2018
CountryUnited States
CitySanta Barbara
Period8/19/188/23/18

Keywords

  • Homomorphic encryption
  • Implementation
  • Linear transformations

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Faster homomorphic linear transformations in HElib'. Together they form a unique fingerprint.

  • Cite this

    Halevi, S., & Shoup, V. (2018). Faster homomorphic linear transformations in HElib. In A. Boldyreva, & H. Shacham (Eds.), Advances in Cryptology – CRYPTO 2018 - 38th Annual International Cryptology Conference, 2018, Proceedings (pp. 93-120). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10991 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-96884-1_4