Leveled Functional Bootstrapping via External Product Tree

Zhihao Li; Xuan Shen; Xianhui Lu; Ruida Wang; Yuan Zhao; Zhiwei Wang; Benqiang Wei

Paper 2025/022

Leveled Functional Bootstrapping via External Product Tree

Zhihao Li, Ant Group

Xuan Shen, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS; School of Cyber Security, UCAS

Xianhui Lu, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS; School of Cyber Security, UCAS

Ruida Wang, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS; School of Cyber Security, UCAS

Yuan Zhao, Ant Group

Zhiwei Wang, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS

Benqiang Wei, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS; School of Cyber Security, UCAS

Abstract

Multi-input and large-precision lookup table (LUT) evaluation pose significant challenges in Fully Homomorphic Encryption (FHE). Currently, two modes are employed to address this issue. One is tree-based functional bootstrapping (TFBS), which uses multiple blind rotations to construct a tree for LUT evaluation. The second is circuit bootstrapping, which decomposes all inputs into bits and utilizes a CMux tree for LUT evaluation. In this work, we propose a novel mode that is leveled functional bootstrapping. This mode utilizes the external product tree to perform multi-input functional bootstrapping. We implement TFBS and LFBS within the OpenFHE library. The results demonstrate that our method outperforms TFBS in both computational efficiency and bootstrapping key size. Specifically, for 12-bit and 16-bit input LUTs, our method is approximately two to three orders of magnitude faster than TFBS. Finally, we introduce a novel scheme-switching framework that supports large-precision polynomial and non-polynomial evaluations. The framework leverages digital extraction techniques to enable seamless switching between the BFV and LFBS schemes.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Lookup Table (LUT)Functional Bootstrapping External Product Scheme Switching.
Contact author(s): lzh458070 @ antgroup com
shenxuan @ iie ac cn
luxianhui @ iie ac cn
wangruida @ iie ac cn
caesar zy @ antgroup com
wangzhiwei @ iie ac cn
weibeiqiang @ iie ac cn
History: 2025-01-07: approved; 2025-01-06: received; See all versions
Short URL: https://ia.cr/2025/022
License: CC BY

BibTeX

@misc{cryptoeprint:2025/022,
      author = {Zhihao Li and Xuan Shen and Xianhui Lu and Ruida Wang and Yuan Zhao and Zhiwei Wang and Benqiang Wei},
      title = {Leveled Functional Bootstrapping via External Product Tree},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/022},
      year = {2025},
      url = {https://eprint.iacr.org/2025/022}
}