Paper 2025/261

HasteBoots: Proving FHE Bootstrapping in Seconds

Haofei Liang, Shanghai Jiao Tong University

Xiang Xie, East China Normal University, Primus Lab

Yu Yu, Shanghai Jiao Tong University

Wenting Zheng, Carnegie Mellon University

Yuncong Hu, Shanghai Jiao Tong University

Abstract

Fully Homomorphic Encryption (FHE) enables computations on encrypted data, ensuring privacy for outsourced computation. However, verifying the integrity of FHE computations remains a significant challenge, especially for bootstrapping, the most computationally intensive operation in FHE. Prior approaches, including zkVM-based solutions and general-purpose SNARKs, suffer from inefficiencies, with proof generation time ranging from several hours to days. In this work, we propose HasteBoots, a succinct argument tailored for TFHE with programmable bootstrapping. By designing efficient protocols for arithmetic operations over quotient rings, HasteBoots achieves proof generation in a few seconds for TFHE evaluation with programmable bootstrapping, significantly outperforming the state-of-the-art, Zama (CCS'25). Moreover, HasteBoots supports batching multiple TFHE evaluations and bootstrappings, a feature that prior work cannot practically support due to prohibitive proving cost. HasteBoots can prove a batch of 16 operations within one minute, while maintaining succinct verification, requiring only 126 ms and a proof size of 0.28 MB. Our approach demonstrates the potential for scalable and efficient verifiable FHE, paving the way for practical, privacy-preserving computations.

@misc{cryptoeprint:2025/261,
      author = {Fengrun Liu and Haofei Liang and Xiang Xie and Yu Yu and Wenting Zheng and Yuncong Hu},
      title = {{HasteBoots}: Proving {FHE} Bootstrapping in Seconds},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/261},
      year = {2025},
      url = {https://eprint.iacr.org/2025/261}
}