Ling, S., Tan, B. H. M., Wang, H., Yang, A. S. (2026). Laurent Polynomial-Based Linear Transformations for Improved Functional Bootstrapping. In (Editor), Information Security and Privacy (pp. 46–74). Springer Nature Singapore. https://doi.org/10.1007/978-981-92-3015-0_3
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 O(√ 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 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 Z_t to Z_{p^r} via leveraging the digit extraction algorithm, achieving a theoretical complexity of O(r^2√ p) ciphertext-ciphertext multiplications. Additionally, we enable a multivalued 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×, while noting a 19× slowdown in amortized performance.
License type:
Publisher Copyright
Funding Info:
This research / project is supported by the National Research Foundation, Singapore and Infocomm Media Development Authority - Trust Tech Funding Initiative
Grant Reference no. : NA
This research / project is supported by the National Research Foundation, Singapore and Infocomm Media Development Authority - Trust Tech Funding Initiative
Grant Reference no. : DTC-IGC-01
This research / project is supported by the National Research Foundation, Singapore and Infocomm Media Development Authority - Trust Tech Funding Initiative
Grant Reference no. : DTC-RGC-03
This research / project is supported by the Singapore Ministry of Education - Academic Research Fund Tier 2 Grant
Grant Reference no. : MOE-T2EP20223-0016
Description:
This is a post-peer-review, pre-copyedit version of an article published in Information Security and Privacy. ACISP 2026. Lecture Notes in Computer Science, vol 16793. The final authenticated version is available online at: http://dx.doi.org/https://doi.org/10.1007/978-981-92-3015-0_3.