Large-Plaintext Functional Bootstrapping with Small Parameters for BGV Encoding
摘要
Functional bootstrapping refreshes the noise of a ciphertext and computes a function homomorphically. It is commonly used to calculate activation functions in privacy-preserving machine learning. However, existing functional bootstrapping requires enormous parameters to evaluate any function for a BGV ciphertext of a large plaintext. In this paper, we first introduce a basic functional bootstrapping algorithm for small plaintexts, which requires only one run of FHEW-like bootstrapping, while other similar methods require extra costs. Then, we provide a homomorphic digit decomposition algorithm that reduces the number of involved FHEW-like bootstrapping procedures by half compared with the work of Micciancio and Polyakov (ASIACRYPT 2022). Finally, based on our above algorithms, we propose a functional bootstrapping algorithm for BGV ciphertexts of large plaintexts that supports 64-bit plaintexts when \(N = 4096\) , where N is the largest dimension used. Compared with the latest BGV/BFV-based functional bootstrapping, for a 12-bit plaintext, the bit size of the largest ciphertext modulus is reduced by 867 bits, N is reduced by a factor of 16, and the computational cost is reduced by a factor of 80.