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 BootstrappingFHETFHEFHEW
Contact author(s)
wangruida @ iie ac cn
History
2024-10-10: revised
2024-02-25: received
See all versions
Short URL
https://ia.cr/2024/323
License
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2024/323}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.