Fast and Accurate: Efficient Full-Domain Functional Bootstrap and Digit Decomposition for Homomorphic Computation

Authors

  • Shihe Ma Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing, China
  • Tairong Huang Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China
  • Anyu Wang Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China; Zhongguancun Laboratory, Beijing, China; National Financial Cryptography Research Center, Beijing, China
  • Qixian Zhou Ant Group
  • Xiaoyun Wang Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China; Zhongguancun Laboratory, Beijing, China; National Financial Cryptography Research Center, Beijing, China; Shandong Institute of Blockchain, Jinan, China; Key Laboratory of Cryptologic Technology and Information Security (Ministry of Education), School of Cyber Science and Technology, Shandong University, Qingdao, China

DOI:

https://doi.org/10.46586/tches.v2024.i1.592-616

Keywords:

Homomorphic Encryption, TFHE, FHEW, Functional Bootstrap, FDFB, Homomorphic Decomposition

Abstract

The functional bootstrap in FHEW/TFHE allows for fast table lookups on ciphertexts and is a powerful tool for privacy-preserving computations. However, the functional bootstrap suffers from two limitations: the negacyclic constraint of the lookup table (LUT) and the limited ability to evaluate large-precision LUTs. To overcome the first limitation, several full-domain functional bootstraps (FDFB) have been developed, enabling the evaluation of arbitrary LUTs. Meanwhile, algorithms based on homomorphic digit decomposition have been proposed to address the second limitation. Although these algorithms provide effective solutions, they are yet to be optimized. This paper presents four new FDFB algorithms and two new homomorphic decomposition algorithms that improve the state-of-the-art. Our FDFB algorithms reduce the output noise, thus allowing for more efficient and compact parameter selection. Across all parameter settings, our algorithms reduce the runtime by up to 39.2%. Our homomorphic decomposition algorithms also run at 2.0x and 1.5x the speed of prior algorithms. We have implemented and benchmarked all previous FDFB and homomorphic decomposition algorithms and our methods in OpenFHE.

Downloads

Published

2023-12-04

Issue

Section

Articles

How to Cite

Fast and Accurate: Efficient Full-Domain Functional Bootstrap and Digit Decomposition for Homomorphic Computation. (2023). IACR Transactions on Cryptographic Hardware and Embedded Systems, 2024(1), 592-616. https://doi.org/10.46586/tches.v2024.i1.592-616