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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Large-Plaintext Functional Bootstrapping with Small Parameters for BGV Encoding

  • Yan Xu,
  • Guizhen Zhu,
  • Huaxiong Wang,
  • Li-Ping Wang

摘要

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.