TY - GEN
T1 - Faster homomorphic linear transformations in HElib
AU - Halevi, Shai
AU - Shoup, Victor
N1 - Funding Information:
Supported by the Defense Advanced Research Projects Agency (DARPA) and Army Research Office (ARO) under Contract No. W911NF-15-C-0236.
Publisher Copyright:
© International Association for Cryptologic Research 2018.
PY - 2018
Y1 - 2018
N2 - 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).
AB - 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).
KW - Homomorphic encryption
KW - Implementation
KW - Linear transformations
UR - http://www.scopus.com/inward/record.url?scp=85052405702&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85052405702&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-96884-1_4
DO - 10.1007/978-3-319-96884-1_4
M3 - Conference contribution
AN - SCOPUS:85052405702
SN - 9783319968834
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 93
EP - 120
BT - Advances in Cryptology – CRYPTO 2018 - 38th Annual International Cryptology Conference, 2018, Proceedings
A2 - Boldyreva, Alexandra
A2 - Shacham, Hovav
PB - Springer Verlag
T2 - 38th Annual International Cryptology Conference, CRYPTO 2018
Y2 - 19 August 2018 through 23 August 2018
ER -