[Resource Topic] 2018/244: Faster Homomorphic Linear Transformations in HElib

Welcome to the resource topic for 2018/244

Faster Homomorphic Linear Transformations in HElib

Authors: Shai Halevi, Victor Shoup


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).

ePrint: https://eprint.iacr.org/2018/244

Talk: https://www.youtube.com/watch?v=LXmGVPcCVag

Slides: https://crypto.iacr.org/2018/slides/Faster%20Homomorphic%20Linear%20Transformations%20in%20HElib.pdf

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .