Welcome to the resource topic for 2025/957
Title:
Laurent Polynomial-Based Linear Transformations for Improved Functional Bootstrapping
Authors: San Ling, Benjamin Hong Meng Tan, Huaxiong Wang, Allen Siwei Yang
Abstract:Following Gentry’s seminal work (STOC 2009), Fully Homomorphic Encryption (FHE) has made significant advancements and can even evaluate functions in the bootstrapping process, called functional bootstrapping. Recently, Liu and Wang (ASIACRYPT 2023) proposed a new approach to functional bootstrapping, which bootstrapped ciphertexts in 7ms amortized time. Their methods packed the secret key of the TFHE cryptosystem into a ciphertext of the BFV cryptosystem, followed by performing functional bootstrapping of TFHE within BFV. However, while this yields high amortized efficiency, it faces high latency and computational complexity of \mathcal{O}(\sqrt{t}) ciphertext-ciphertext multiplications due to use of large BFV plaintext primes that serve as the TFHE ciphertext modulus, t = 65537, to maximize SIMD slots.
In this work, we adapt their techniques to achieve lower latency functional bootstrapping by relaxing the requirement for prime BFV plaintext modulus to prime powers, t = p^r. We first introduce an improved linear transformation stage, multiplying Laurent Polynomial packed secret key and ciphertexts, a_{ij} and sk_j, evaluating a \mathbb{Z}_{p^r} linear map. With this, we reduce the number of operations needed to evaluate the linear phase of bootstrapping. Finally, we generalize their functional bootstrapping procedure from plaintext space \mathbb{Z}_t to \mathbb{Z}_{p^r} via leveraging the digit extraction algorithm, achieving a theoretical complexity of \mathcal{O}(r^2\sqrt{p}) ciphertext-ciphertext multiplications. Additionally, we enable a multi-valued bootstrapping scheme that permits the evaluation of multiple functions over a shared input. To the best of our knowledge, this is the first demonstration of such a method for TFHE ciphertexts that relies predominantly on BFV-based techniques.
In our experiments, we achieve overall runtimes as low as 49.873s, representing latency reductions of at least 26\times, while noting a 19\times slowdown in amortized performance.
ePrint: https://eprint.iacr.org/2025/957
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 .