Welcome to the resource topic for 2025/1104
Title:
Better GBFV Bootstrapping and Faster Encrypted Edit Distance Computation
Authors: Robin Geelen, Frederik Vercauteren
Abstract:We propose a new iterative method to convert a ciphertext from the Generalized BFV (GBFV) to the regular BFV scheme. In particular, our conversion starts from an encrypted plaintext that lives in a large cyclotomic ring modulo a small-norm polynomial t(x), and gradually changes the encoding to a smaller cyclotomic ring modulo a larger integer p. Previously, only a trivial conversion method was known, which did not change the underlying cyclotomic ring.
Using our improved conversion algorithm, we can bootstrap the GBFV scheme almost natively, in the sense that only a very small fraction of the operations is computed inside regular BFV. Specifically, we evaluate (an adapted version of) the slot-to-coefficient transformation entirely in the GBFV scheme, whereas the previous best method used the BFV scheme for that transformation. This insight allows us to bootstrap either with less noise growth, or much faster than the state-of-the-art.
We implement our new bootstrapping in Microsoft SEAL. Our experiments show that, for the same remaining noise budget, our bootstrapping runs in only 800 ms when working with ciphertexts containing 1024 slots over \mathbb{F}_{p} with p = 2^{16}+1. This is 1.6\times faster than the state-of-the-art.
Finally, we use our improved GBFV bootstrapping in an application that computes an encrypted edit distance. Compared to the recent TFHE-based Leuvenshtein algorithm, our GBFV version is almost two orders of magnitude faster in the amortized sense.
ePrint: https://eprint.iacr.org/2025/1104
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .