<p>Traditional fully homomorphic encryption(FHE) schemes allow computation only on data encrypted under the same public key. Multi-Key Fully Homomorphic Encryption (MKFHE) enables arbitrary operations on data encrypted with different public keys, allowing all participating users jointly decrypting the final ciphertext. The multi-key BFV FHE scheme inherits BFV’s advantages in ring element encryption and scale invariance. Nonetheless, it also has some disadvantages, such as additional noise generated during the relinearization process, the need for costly transformations during the external product process, and the requirement for a Common Reference String (CRS). In this paper, we investigate the MKFHE scheme for RLWE-based BFV. Firstly, we improve the modulus size of the evaluation key and the public key to construct a modulus enchancement relinearization method, which can significantly reduce the noise generated during the relinearization process. Secondly, we propose to use an inner product via Gadget decomposition in the relinearization based on the MK-BFV scheme instead of the original outer product operation, which can reduce the complexity of the NTT operation to <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="42400_2024_337_Article_IEq1.gif" Format="GIF" Height="33" Rendition="HTML" Resolution="72" Type="Linedraw" Width="154" /> </InlineMediaObject> <EquationSource Format="TEX">$\left( {d + 2\tilde{d}} \right)r^{\prime } /\left( {d + 2} \right)\tilde{l}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfenced close=")" open="("> <mrow> <mi>d</mi> <mo>+</mo> <mn>2</mn> <mover accent="true"> <mi>d</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mfenced> <msup> <mi>r</mi> <mo>′</mo> </msup> <mo stretchy="false">/</mo> <mfenced close=")" open="("> <mrow> <mi>d</mi> <mo>+</mo> <mn>2</mn> </mrow> </mfenced> <mover accent="true"> <mi>l</mi> <mo stretchy="false">~</mo> </mover> </mrow> </math></EquationSource> </InlineEquation> of the original one. Finally, we propose a MK-BFV without CRS on the basis of the previous ones, which enhances the user's control over his own key.</p>

An efficient multi-key BFV fully homomorphic encryption scheme with optimized relinearization

期刊论文
出版模式：

开放获取
发表日期：

2025年6月26日

查看全文

Sai Hu,
Ruwei Huang,
Liang Zhou

摘要

Traditional fully homomorphic encryption(FHE) schemes allow computation only on data encrypted under the same public key. Multi-Key Fully Homomorphic Encryption (MKFHE) enables arbitrary operations on data encrypted with different public keys, allowing all participating users jointly decrypting the final ciphertext. The multi-key BFV FHE scheme inherits BFV’s advantages in ring element encryption and scale invariance. Nonetheless, it also has some disadvantages, such as additional noise generated during the relinearization process, the need for costly transformations during the external product process, and the requirement for a Common Reference String (CRS). In this paper, we investigate the MKFHE scheme for RLWE-based BFV. Firstly, we improve the modulus size of the evaluation key and the public key to construct a modulus enchancement relinearization method, which can significantly reduce the noise generated during the relinearization process. Secondly, we propose to use an inner product via Gadget decomposition in the relinearization based on the MK-BFV scheme instead of the original outer product operation, which can reduce the complexity of the NTT operation to $\left( {d + 2\tilde{d}} \right)r^{\prime } /\left( {d + 2} \right)\tilde{l}$ $(d + 2 \tilde{d}) r^{'} / (d + 2) \tilde{l}$ of the original one. Finally, we propose a MK-BFV without CRS on the basis of the previous ones, which enhances the user's control over his own key.