International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Fast Blind Rotation for Bootstrapping FHEs

Authors:
Binwu Xiang , State Key Laboratory of Information Security
Jiang Zhang , State Key Laboratory of Cryptology
Yi Deng , State Key Laboratory of Information Security
Yiran Dai , State Key Laboratory of Information Security
Dengguo Feng , State Key Laboratory of Cryptology
Download:
DOI: 10.1007/978-3-031-38551-3_1 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: Blind rotation is one of the key techniques to construct fully homomorphic encryptions with the best known bootstrapping algorithms running in less than one second. Currently, the two main approaches, namely, AP and GINX, for realizing blind rotation are first introduced by Alperin-Sheriff and Peikert (CRYPTO 2014) and Gama, Izabachene, Nguyen and Xie (EUROCRYPT 2016), respectively. In this paper, we propose a new blind rotation algorithm based on a GSW-like encryption from the NTRU assumption. Our algorithm has performance asymptotically independent from the key distributions, and outperforms AP and GINX in both the evaluation key size and the computational efficiency (especially for large key distributions). By using our blind rotation algorithm as a building block, we present new bootstrapping algorithms for both LWE and RLWE ciphertexts. We implement our bootstrapping algorithm for LWE ciphertexts, and compare the actual performance with two bootstrapping algorithms, namely, FHEW/AP by Ducas and Micciancio (EUROCRYPT 2015) and TFHE/GINX by Chillotti, Gama, Georgieva and Izabach\`ene (Journal of Cryptology 2020), that were implemented in the OpenFHE library. For parameters with ternary key distribution at 128-bit security, our bootstrapping only needs to store evaluation key of size 18.65MB for blind rotation, which is about 89.8 times smaller than FHEW/AP and 2.9 times smaller than TFHE/GINX. Moreover, our bootstrapping can be done in 112ms on a laptop, which is about 3.2 times faster than FHEW/AP and 2.1 times faster than TFHE/GINX. More improvements are available for large key distributions such as Gaussian distributions.
BibTeX
@inproceedings{crypto-2023-33119,
  title={Fast Blind Rotation for Bootstrapping FHEs},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-38551-3_1},
  author={Binwu Xiang and Jiang Zhang and Yi Deng and Yiran Dai and Dengguo Feng},
  year=2023
}