Functional bootstrapping is for a cloud server to refresh the error of a ciphertext and homomorphically evaluate a public function f without decryption. Furthermore, in some applications, a cloud server needs to perform functional bootstrapping without knowing f but given a certain encryption of f. Currently, the best amortized asymptotic complexity of the amortized variants of functional bootstrapping is \(\tilde{O}(1)\) per message for a public function. However, there is no amortized algorithm for an encrypted function. In this paper, we propose a novel amortized functional bootstrapping algorithm whether the function f is public or encrypted. Firstly, we extend the amortized homomorphic automorphism technique of LW23 (Liu and Wang, EUROCRYPT 2023) to perform different automorphisms and key switching on multiple ciphertexts simultaneously. Then, by using our extended automorphism technique, we improve the homomorphic inverse number theoretic transform (NTT) technique of Guimarães et al. (ASIACRYPT 2023) to reduce costs. Next, we combine the amortized bootstrapping framework of Micciancio and Sorrell (ICALP 2018) with the above improved inverse NTT technique to construct our amortized functional bootstrapping algorithm whose amortized cost is \(\tilde{O}(1)\) . Moreover, the sub-Gaussian parameters of the output errors in our algorithm are \(\tilde{O}(E N^{9.375})\) where N is the number of input ciphertexts and E is the sub-Gaussian parameter of the errors of bootstrapping keys, and thus they are independent of f. In particular, they are reduced by a factor of \(\tilde{O}(|f(x)|N^{28.625})\) for any public function f, compared with the work of Liu and Wang (ASIACRYPT 2023).

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

Amortized Functional Bootstrapping for Homomorphic Evaluation of Encrypted Functions

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

摘要

Functional bootstrapping is for a cloud server to refresh the error of a ciphertext and homomorphically evaluate a public function f without decryption. Furthermore, in some applications, a cloud server needs to perform functional bootstrapping without knowing f but given a certain encryption of f. Currently, the best amortized asymptotic complexity of the amortized variants of functional bootstrapping is \(\tilde{O}(1)\) per message for a public function. However, there is no amortized algorithm for an encrypted function. In this paper, we propose a novel amortized functional bootstrapping algorithm whether the function f is public or encrypted. Firstly, we extend the amortized homomorphic automorphism technique of LW23 (Liu and Wang, EUROCRYPT 2023) to perform different automorphisms and key switching on multiple ciphertexts simultaneously. Then, by using our extended automorphism technique, we improve the homomorphic inverse number theoretic transform (NTT) technique of Guimarães et al. (ASIACRYPT 2023) to reduce costs. Next, we combine the amortized bootstrapping framework of Micciancio and Sorrell (ICALP 2018) with the above improved inverse NTT technique to construct our amortized functional bootstrapping algorithm whose amortized cost is \(\tilde{O}(1)\) . Moreover, the sub-Gaussian parameters of the output errors in our algorithm are \(\tilde{O}(E N^{9.375})\) where N is the number of input ciphertexts and E is the sub-Gaussian parameter of the errors of bootstrapping keys, and thus they are independent of f. In particular, they are reduced by a factor of \(\tilde{O}(|f(x)|N^{28.625})\) for any public function f, compared with the work of Liu and Wang (ASIACRYPT 2023).