## 5 Parameter and Performance Analysis and Comparison
Their designs also involve storing repeated random samples of vectors \(\mathbf{a}_{l}\in U\big{(}R_{Q_{l}}^{l}\big{)}\), where \(l=L,\ldots,0\), in both the public parameters and the public keys, which results in redundant storage overhead. Our schemes optimize these issues, reducing the public key size to approximately one-quarter of that in [16; 17] for non-batch scenarios. Compared to [19], our \(\mathbf{MK-BGV}\) scheme has slightly larger public key and evaluation key sizes, which is due to the fact that in BFV(CKKS)-type schemes, each party uses the same secret key across all circuit levels. However, this introduces the need for an additional circular security assumption, which poses the risk of leaking secret keys of the participants. Since this circular security assumption has not been rigorously proven, our scheme avoids this potential security issue by rotating the secret keys for all parties at each circuit level. Scheme [24] adopts an accumulation-style key technique from threshold FHE, achieving extended ciphertexts and evaluation keys whose sizes are independent of the number of participating parties. Furthermore, the number of ring multiplications required in the tensor product operation is independent of the number of parties. However, this design also inherits structural complexities and limitations similar to those observed in threshold FHE constructions. Specifically, their scheme requires the computation of additional types of intricate parameters--such as joint public keys, joint evaluation public keys, and refreshing keys--none of which are required in either of our constructions. As in [16; 17], each party in [24] must locally generate its own evaluation key generation materials (referred to as partial switching keys), which are then aggregated to derive joint evaluation keys. In their scheme, a key distinction is that any change in the set of participating parties necessitates the recomputation of not only the joint evaluation key but also all of the aforementioned parameters. This design leads to even higher interaction frequency and complexity, as well as greater computational and storage overheads for each party, compared to [16; 17], which highlights the efficiency advantages of our design in minimizing coordination, computation, and storage overheads. Moreover, each ciphertext extension in [24] requires the use of refreshing keys and key switching, whereas our ciphertext extension algorithms--\(\mathbf{MK-BGV.CText}\) and \(\mathbf{BMK-BGV.CText}\)--complete this operation using only \(O(n)\) lightweight assignment operations, making our method significantly more efficient than that of [24]. \begin{table}
\begin{tabular}{c c c c c} \hline \hline \multirow{2}{*}{**Scheme**} & \multirow{2}{*}{
\begin{tabular}{c} **Evaluation Key Generation** \\ **Material Size** \\ \end{tabular} } & \multicolumn{2}{c}{**Computational Complexity (Number of Scalar Operations)**} & \multicolumn{1}{c}{**Number of Gadget**} \\ \cline{3-5}  & & **Joint Evaluation Key** & **Homomorphic** & **Decompositions in** \\  & & **Generation** & **Multiplication** & **Key Switching** \\ \hline CZW17 [16] & \(24(L+1)l^{2}nN[\log Q]\) & \(O(n^{3}N)\) & \(O(n^{3}N)\) & \(O(n^{2})\) \\ LZY+19 [17] & \(8(L+1)tnN[\log Q]\) & \(O(n^{3}N)\) & \(O(n^{3}N)\) & \(O(n^{2})\) \\ CCS19 [18] & – & \(O(n^{2}N^{2})\) & \(O(n^{2}N^{2})\) & \(O(nN)\) \\ CDKS19 [19] & – & – & \(O(n^{2}N)\) & \(O(n^{2})\) \\ ZCC+21 [24] & \(2 nN[\log PQ]\) & \(O(nN)\) & \(O(N)\) & \(O(nt)\) \\ \((\mathbf{B})\mathbf{MK-BGV}\) & – & – & \(O(nN)\) & \(O(n)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Comparison of homomorphic multiplication and key switching (relinearization) algorithm performance between recent efficient MKFHE schemes. The notation is consistent with Table 1.