Cryptology ePrint Archive: Report 2022/198

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

Yongwoo Lee and Daniele Micciancio and Andrey Kim and Rakyong Choi and Maxim Deryabin and Jieun Eom and Donghoon Yoo

Abstract: 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 are both critical for a number of important applications (like threshold and some multi-key homomorphic encryption (HE) schemes), and provides 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 are less standard and restrict 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 and further improves on them: support for arbitrary secret key distributions at no additional runtime costs, while using small evaluation keys (even smaller than GINX). 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. We demonstrate the practicality of the proposed methods by building a prototype implementation within the PALISADE open-source HE library. Our experimental results show that our methods have minimal overhead, and improve on the practical performance of previous schemes, by factors ranging from small constants (already in the case of ternary keys) to an order of magnitude or more (e.g., when comparing to FHEW evaluation key size for arbitrary secret keys.) We illustrate the benefits of our method by providing a simple construction of threshold HE based on FHEW.

Category / Keywords: public-key cryptography / Blind Rotation, Bootstrapping, Fully Homomorphic Encryption (FHE), Threshold Homomorphic Encryption.

Date: received 18 Feb 2022

Contact author: yw0803 lee at samsung com, daniele at cs ucsd edu, andrey kim at samsung com, rakyong choi at samsung com, max deriabin at samsung com, jieun eom at samsung com, say yoo at samsung com

Available format(s): PDF | BibTeX Citation

Version: 20220220:204153 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]