Paper 2023/1564

Fast Blind Rotation for Bootstrapping FHEs

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

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. \qquad 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.

Available format(s)
Publication info
Published elsewhere. CRYPTO 2023
LatticesFully Homomorphic EncryptionBootstrappingBlind Rotations
Contact author(s)
xiangbinwu @ iie ac cn
zhangj @ sklc org
deng @ iie ac cn
daiyiran @ iie ac cn
fengdg @ 263 net
2023-10-13: approved
2023-10-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Binwu Xiang and Jiang Zhang and Yi Deng and Yiran Dai and Dengguo Feng},
      title = {Fast Blind Rotation for Bootstrapping {FHEs}},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1564},
      year = {2023},
      doi = {10.1007/978-3-031-38551-3_1},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.