Research Article
Optimization of Functional Bootstraps with Large LUT and Packing Key Switching
@INPROCEEDINGS{10.1007/978-3-031-64948-6_22, author={Keyi Liu and Chungen Xu and Bennian Dou and Lei Xu}, title={Optimization of Functional Bootstraps with Large LUT and Packing Key Switching}, proceedings={Security and Privacy in Communication Networks. 19th EAI International Conference, SecureComm 2023, Hong Kong, China, October 19-21, 2023, Proceedings, Part I}, proceedings_a={SECURECOMM}, year={2024}, month={10}, keywords={Homomorphic Encryption Lookup Table Key Switching TFHE}, doi={10.1007/978-3-031-64948-6_22} }- Keyi Liu
Chungen Xu
Bennian Dou
Lei Xu
Year: 2024
Optimization of Functional Bootstraps with Large LUT and Packing Key Switching
SECURECOMM
Springer
DOI: 10.1007/978-3-031-64948-6_22
Abstract
Homomorphic encryption can perform calculations on encrypted data, which can protect the privacy of data during the usage of data.FunctionalBootstrapsalgorithm proposed by I. Chillotti et al. can compute arbitrary functions represented as lookup table whilst bootstrapping, but the computational efficiency ofFunctionalBootstrapswith large lookup table or highly precise functions is not high enough. To tackle this issue, we propose a new Tree-BML algorithm. Our Tree-BML algorithm accelerates the computation ofFunctionalBootstrapswith large LUT by compressing more LWE ciphertexts to a TRLWE ciphertext and utilizing the PBSmanyLUT algorithm which was proposed by I. Chillotti et al. in 2021. The Tree-BML algorithm reduces the running time of LUT computation by(72.09\%)(depend on parameters) compared to(Tree\text {-}based)method (Antonio Guimarães et al., 2021). Additionally, we introduce a new TLWE-to-TRLWE Packing Key Switching algorithm which reduces the storage space required and communication overhead of homomorphic encryption algorithm by only generating one of those key-switching key ciphertexts of polynomials with the same non-zero coefficient values but only those values located in different slots. Our algorithm reduces the key-switching key size by(75\%)compared to Base-aware TLWE-to-TRLWE Key Switching algorithm. Finally, we obtain that our algorithms does not introduce new output error through theoretical and experiment result.
