International Association
for Cryptologic Research

BGV and BFV are among the most widely used fully homomorphic encryption (FHE) schemes, supporting evaluations over a finite field. To evaluate a circuit with arbitrary depth, bootstrapping is needed. However, despite the recent progress, bootstrapping of BGV/BFV still remains relatively impractical, compared to other FHE schemes. In this work, we inspect the BGV/BFV bootstrapping procedure from a different angle. We provide a generalized bootstrapping definition that relaxes the correctness requirement of regular bootstrapping, allowing constructions that support only certain kinds of circuits with arbitrary depth. In addition, our definition captures a form of functional bootstrapping. In other words, the output encrypts a function evaluation of the input instead of the input itself. Under this new definition, we provide a bootstrapping procedure supporting different types of functions. Our construction is 1-2 orders of magnitude faster than the state-of-the-art BGV/BFV bootstrapping algorithms, depending on the evaluated function. Of independent interest, we show that our technique can be used to improve the batched FHEW/TFHE bootstrapping construction introduced by Liu and Wang (Asiacrypt 2023). Our optimization provides a speed-up of 6x in latency and 3x in throughput for binary gate bootstrapping and a plaintext-space-dependent speed-up for functional bootstrapping with plaintext space smaller than Z_{512}.

Amortized bootstrapping offers a way to refresh multiple ciphertexts of a fully homomorphic encryption scheme in parallel more efficiently than refreshing a single ciphertext at a time. Micciancio and Sorrell (ICALP 2018) first proposed this technique to bootstrap n LWE ciphertexts at a time, reducing the total cost from \tilde{O}(n^2) to \tilde{O}(3^\epsilon n^{1+1/\epsilon}) for arbitrary \epsilon > 0. Several recent follow-up works have further improved the asymptotic cost. Despite these amazing progresses in theoretical efficiency, none of these works have demonstrated the practicality of batched LWE ciphertext bootstrapping. Moreover, most of these works only support limited functional bootstrapping, i.e., they only allow evaluating a specific type of function when bootstrapping. In this work, we propose a construction that is not only asymptotically efficient (requiring only \tilde{O}(n) polynomial multiplications for bootstrapping of n LWE ciphertexts) but also concretely efficient. We have our scheme implemented as a C++ library and show that it takes <5ms per LWE ciphertext to bootstrap for a binary gate, which is an order of magnitude faster than the state-of-the-art C++ implementation on LWE ciphertext bootstrapping in OpenFHE. Furthermore, our construction supports batched arbitrary functional bootstrapping. For a 9-bit messages space, our scheme takes ~6.7ms per LWE ciphertext to evaluate an arbitrary function with bootstrapping, which is about two to three magnitudes faster than all the existing schemes that achieve a similar functionality and message space.