Circuit Bootstrapping: Faster and Smaller

Ruida Wang; Yundi Wen; Zhihao Li; Xianhui Lu; Benqiang Wei; Kun Liu; Kunpeng Wang

Paper 2024/323

Circuit Bootstrapping: Faster and Smaller

Ruida Wang

, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Yundi Wen, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China

Zhihao Li, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Xianhui Lu, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China

Benqiang Wei, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Kun Liu, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Kunpeng Wang, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China

Abstract

We present a novel circuit bootstrapping algorithm that outperforms the state-of-the-art TFHE method with 9.9× speedup and 15.6× key size reduction. These improvements can be attributed to two technical contributions. Firstly, we redesigned the circuit bootstrapping workflow to operate exclusively under the ring ciphertext type, which eliminates the need of conversion between LWE and RLWE ciphertexts. Secondly, we improve the LMKC+ blind rotation algorithm by reducing the number of automorphisms, then propose the first automorphism type multi-value functional bootstrapping. These automorphism-based techniques lead to further key size optimization, and are of independent interest besides circuit bootstrapping. Based our new circuit bootstrapping we can evaluate AES-128 in 26.2s (single thread), achieving 10.3× speedup compared with the state-of-the-art TFHE-based approach.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A minor revision of an IACR publication in EUROCRYPT 2024
Keywords: Circuit Bootstrapping FHE TFHE FHEW
Contact author(s): wangruida @ iie ac cn
History: 2024-02-26: approved; 2024-02-25: received; See all versions
Short URL: https://ia.cr/2024/323
License: CC BY

BibTeX

@misc{cryptoeprint:2024/323,
      author = {Ruida Wang and Yundi Wen and Zhihao Li and Xianhui Lu and Benqiang Wei and Kun Liu and Kunpeng Wang},
      title = {Circuit Bootstrapping: Faster and Smaller},
      howpublished = {Cryptology ePrint Archive, Paper 2024/323},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/323}},
      url = {https://eprint.iacr.org/2024/323}
}