Cryptology ePrint Archive: Report 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).

Category / Keywords: public-key cryptography / Homomorphic encryption, Implementation, Linear transformations, bootstrapping

Original Publication (in the same form): IACR-CRYPTO-2018

Date: received 4 Mar 2018, last revised 11 May 2019

Contact author: shaih at alum mit edu

Available format(s): PDF | BibTeX Citation

Version: 20190511:130501 (All versions of this report)

Short URL: ia.cr/2018/244