Paper 2022/198

Efficient FHEW Bootstrapping with Small Evaluation Keys, and Applications to Threshold Homomorphic Encryption

Yongwoo Lee, Samsung Advanced Institute of Technology
Daniele Micciancio, University of California, San Diego
Andrey Kim, Samsung Advanced Institute of Technology
Rakyong Choi, Samsung Advanced Institute of Technology
Maxim Deryabin, Samsung Advanced Institute of Technology
Jieun Eom, Samsung Advanced Institute of Technology
Donghoon Yoo, Samsung Advanced Institute of Technology

The FHEW fully homomorphic encryption scheme (Ducas and Micciancio, Eurocrypt 2015) and its TFHE variant (Chillotti et al., Asiacrypt 2016) are the best-known methods to perform bit-level homomorphic computations on encrypted data. There are two competing bootstrapping approaches to FHEW-like schemes: the AP bootstrapping method (Alperin-Sheriff and Peikert, Crypto 2014) which is the basis of the original FHEW scheme, and the GINX bootstrapping method (Gama et al., Eurocrypt 2016), adopted by TFHE. An attractive feature of the AP/FHEW method is that it supports arbitrary secret key distributions, which is critical for a number of important applications (like threshold and some multi-key homomorphic encryption (HE) schemes) and provides potentially better security guarantees. On the other hand, GINX/TFHE bootstrapping uses much smaller evaluation keys, but it is directly applicable only to binary secret keys, which restricts the scheme's applicability. (Extensions of GINX/TFHE bootstrapping to arbitrary keys are known, but they incur a substantial performance penalty.) In this paper, we present a new bootstrapping procedure for FHEW-like schemes that achieves the best features of both schemes: support for arbitrary secret key distributions at no additional runtime costs, while using small evaluation keys. As an added benefit, our new bootstrapping procedure results in smaller noise growth than both AP and GINX, regardless of the key distribution. Our improvements are both theoretically significant (offering asymptotic savings, up to a $O(\log n)$ multiplicative factor, either on the running time or public evaluation key size), and practically relevant. For example, for a concrete 128-bit target security level, we show how to decrease the evaluation key size of the best previously known scheme by more than 30%, while also slightly reducing the running time. We demonstrate the practicality of the proposed methods by building a prototype implementation within the PALISADE open-source HE library. We provide optimized parameter sets and implementation results showing that the proposed algorithm has the best performance among all known FHEW bootstrapping methods in terms of runtime and key size. We illustrate the benefits of our method by sketching a simple construction of threshold HE based on FHEW.

Available format(s)
Public-key cryptography
Publication info
Blind Rotation Bootstrapping Fully Homomorphic Encryption (FHE) Threshold Homomorphic Encryption.
Contact author(s)
yw0803 lee @ samsung com
daniele @ cs ucsd edu
andrey kim @ samsung com
rakyong choi @ samsung com
max deriabin @ samsung com
jieun eom @ samsung com
donghoon yoo @ desilo ai
2022-10-14: last of 2 revisions
2022-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yongwoo Lee and Daniele Micciancio and Andrey Kim and Rakyong Choi and Maxim Deryabin and Jieun Eom and Donghoon Yoo},
      title = {Efficient FHEW Bootstrapping with Small Evaluation Keys, and Applications to Threshold Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2022/198},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.