| 摘要: |
| 多密钥全同态加密方案能够对被不同密钥加密的隐私数据进行密态计算，可以帮助多个用户安全地完成联邦学习等联合计算任务。特别地，其中的多密钥自举技术可以降低密文噪声，使方案支持深度神经网络推断等更复杂的运算。多密钥自举的计算代价较大，利用自举完成部分计算任务将减少计算资源的浪费。但是，现有的多密钥自举算法只能对单比特明文同态执行布尔运算，计算能力十分有限。在本文中，我们提出了一种多密钥可编程自举算法MK-PBS。该算法可以降低密文噪声，并且对多比特明文同态计算任意函数。首先，我们结合Akin等人的多密钥FHEW型方案（ESORICS 2023）与BGV同态加密方案的明文编码方式（Brakerski等人, ITCS 2012），设计了一种基于BGV编码的多密钥全同态加密方案，作为算法MK-PBS的构造基础。然后，我们利用私钥之间的共性，改进了自举中的多密钥切换，将其计算量与密钥大小分别缩小了约2倍和4倍。接着，我们遵循FHEW自举框架，结合上述技术构造算法MK-PBS，使之同态计算任意函数的代价仅为一次多密钥FHEW型自举，而且是参与方个数K的线性量级。另外，我们还提出了一种生成函数的多密钥密文的算法，其输出可以被算法MK-PBS用于同态计算该函数。最后，我们利用数论变换实现了算法MK-PBS。对于同态布尔运算，与Akin等人的工作比，算法MK-PBS以稍长的执行时间为代价，将自举误差的标准差与密文模数的比值缩小1.1~11倍（K = 2~32），使输出密文支持更多运算。 |
| 关键词: 全同态加密 自举 密钥切换 数论变换 |
| DOI： |
| 投稿时间：2025-04-08修订日期：2025-08-25 |
| 基金项目:国家自然科学基金项目（面上项目，重点项目，重大项目） |
|
| Multi-Key Programmable Bootstrapping Supporting Homomorphic Evaluation of Arbitrary Functions |
|
XU Yan, WANG Li-Ping
|
| (Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS) |
| Abstract: |
| Multi-key fully homomorphic encryption (MKFHE) schemes enable secure computation on encrypted data protected by distinct keys and help multiple users securely accomplish collaborative computation tasks, like federated learning. Particularly, the multi-key bootstrapping in the schemes reduces ciphertext noise to support more complex operations, such as deep neural network inference. The bootstrapping incurs high costs, and using it for partial computations can mitigate the waste of computing resources. However, existing multi-key bootstrapping algorithms only evaluates Boolean functions on single-bit plaintexts. In this paper, we propose a multi-key programmable bootstrapping algorithm, MK-PBS, that reduces ciphertext noise and homomorphically computes arbitrary functions over multi-bit plaintexts. First, we design a BGV-encoded MKFHE scheme by combining Akin et al.'s multi-key FHEW-like scheme (ESORICS 2023) and the plaintext encoding of the BGV scheme (Brakerski et al., ITCS 2012), serving as the foundation for MK-PBS. Next, we improve the multi-key switching in bootstrapping by using commonalities among secret keys, reducing its computational cost and key size by a factor of about 2 and 4, respectively. Then, following the FHEW-like bootstrapping framework, we use the above techniques to construct MK-PBS, whose cost of evaluating an arbitrary function is only one run of multi-key FHEW bootstrapping, linear to the number of parties (K). Besides, we propose an algorithm to output a multi-key ciphertext of a function, and the output can be used to evaluate this function by MK-PBS. Finally, we implement MK-PBS using the Number Theoretic Transform. For Boolean operations, compared to Akin et al.'s work, we reduce the ratio of the standard deviation of the bootstrapping error to the ciphertext modulus by a factor of 1.1~11.1 (K = 2~32), allowing the output ciphertexts to support more operations at the cost of slightly longer runtime. |
| Key words: fully homomorphic encryption bootstrapping key switching number theoretic transform |
