Fengrun Liu, Carnegie Mellon University; Haofei Liang, Shanghai Jiao Tong University; Xiang Xie, East China Normal University and Primus Labs; Yu Yu, Shanghai Jiao Tong University; Wenting Zheng, Carnegie Mellon University; Yuncong Hu, Shanghai Jiao Tong University
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.
USENIX Security '26 Open Access Sponsored by
King Abdullah University of Science and Technology (KAUST)
Open Access Media
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.
author = {Fengrun Liu and Haofei Liang and Xiang Xie and Yu Yu and Wenting Zheng and Yuncong Hu},
title = {{HasteBoots}: Proving {TFHE} Programmable Bootstrapping in Seconds},
booktitle = {35th USENIX Security Symposium (USENIX Security 26)},
year = {2026},
isbn = {978-1-939133-58-8},
address = {Baltimore, MD},
pages = {41--60},
url = {https://www.usenix.org/conference/usenixsecurity26/presentation/liu-fengrun},
publisher = {USENIX Association},
month = aug
}