International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Circuit Bootstrapping: Faster and Smaller

Authors:
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; School of Cyber Security, University of 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; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Download:
DOI: 10.1007/978-3-031-58723-8_12 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2024
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.
BibTeX
@inproceedings{eurocrypt-2024-33973,
  title={Circuit Bootstrapping: Faster and Smaller},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-58723-8_12},
  author={Ruida Wang and Yundi Wen and Zhihao Li and Xianhui Lu and Benqiang Wei and Kun Liu and Kunpeng Wang},
  year=2024
}