CryptoDB
Relaxed Functional Bootstrapping: A New Perspective on BGV/BFV Bootstrapping
| Authors: |
|
|---|---|
| Download: | |
| Conference: | ASIACRYPT 2024 |
| Abstract: | 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}. |
BibTeX
@inproceedings{asiacrypt-2024-34514,
title={Relaxed Functional Bootstrapping: A New Perspective on BGV/BFV Bootstrapping},
publisher={Springer-Verlag},
author={Zeyu Liu and Yunhao Wang},
year=2024
}