## 3 Preliminaries
### Additive Homomorphic Encryption (Additive HE)  
[PERSON] et al. first proposed homomorphic encryption (HE) in 1978 [1], and this encryption performs homomorphic operations on ciphertexts without decryption. This is equivalent to performing the corresponding operations on plaintext, ensuring data privacy while also maintaining data availability. Depending on the supported mathematical operations, HE can be classified into partial (additive or multiplicative) homomorphic encryption (PHE) [26; 27], fully homomorphic encryption (FHE) [2] and somewhat homomorphic encryption (SWHE) [28; 29; 30]. PHE supports only one type of operation (either additive or multiplicative) on the ciphertext. FHE supports both additive and multiplicative operations but with high computational costs. SWHE supports limited multiplication and addition operations, with lower computational costs compared with FHE. The following describes the additive homomorphic encryption scheme that we use based on [24], which contains five algorithms: \(HE=(Setup,KeyGen,Enc,Dec,Eval)\). The details are as follows:  
* \(Setup(\lambda)\to pp\): The security parameter \(\lambda\) is taken as input, and two \(\lambda\)-bit large prime numbers, \(p^{{}^{\prime}},q^{{}^{\prime}}\), are chosen. Then, we have \(N=pq\), where \(p=2p^{{}^{\prime}}+1\) and \(q=2q^{{}^{\prime}}+1\). A generator \(g\in\mathbb{Z}_{N^{2}}^{*}\) is randomly sampled, and then the public parameters \(pp=(N,g)\) are output. * \(KeyGen(pp)\rightarrow(pk,sk)\): The public parameters \(pp\) are taken as input. According to \(pp=(N,g)\), \(a\xleftarrow{\xi}\mathbb{Z}_{N^{2}}\) is randomly sampled. Then, the public/secret key pair \((pk=g^{a}\ mod\ N^{2},sk=a)\) is output. * \(Enc(m,pk)\to c\): For a message \(m\in\mathbb{Z}_{N}\), \(r\xleftarrow{\xi}\mathbb{Z}_{N^{2}}\) is sampled. The message \(m\) is encrypted with public key \(pk=g^{a}\) and outputs ciphertext \(c=(A,B)\), where \(A=g^{ar}\ mod\ N^{2}\), \(B=g^{r}(1+mN)\ mod\ N^{2}\). * \(Dec(c,sk)\to m\): For the ciphertext \(c=(A,B)\), secret key \(sk=a\) is used for decryption, and the output message is \(m=\frac{B/(A^{\frac{1}{2}})-1\ mod\ N^{2}}{N}\). \begin{table}
\begin{tabular}{c c} \hline \hline
**Notations** & **Descriptions** \\ \hline \(\mathbf{x}\) & The lowercase bold letters denote vectors where \(x_{i}\) indexes the \(i\)-th element \\ \(\mathbf{\mathrm{M}}\) & The uppercase bold letters denote matrices where \(M_{i,j}\) indexes the \((i,j)\)-th element \\ \(\mathbf{x}^{\top}\) & The transpose of vector \(\mathbf{x}\) \\ \(\mathbf{x}\ldots\mathbf{y}\) & The dot product of two vectors, \(\mathbf{x}=(x_{1},\ldots,x_{n})\) and \(\mathbf{y}=(y_{1},\ldots,y_{n})\), \\  & where \(\mathbf{x}\cdot\mathbf{y}=\sum_{i=1}^{n}x_{i}y_{i}\) \\ \(\mathbf{\mathrm{M}}\cdot\mathbf{x}\) & The matrix–vector multiplication of \(\mathbf{\mathrm{M}}\) and \(\mathbf{x}\) \\ \(x\xleftarrow{\xi}S\) & Uniformly sample \(x\) from a set \(S\) at random. \\ \(\mathbb{N}\) & The set of all natural numbers \\ \([n]\) & The set \(\{1,\ldots,n\}\), where \(n\in\mathbb{N}\) \\ \(\lambda\) & The security parameter \\ \(p,q\) & The odd primes \\ \(\mathbb{Z}_{N}\) & A group under addition modulo N \\ \(\mathbb{Z}_{N}^{*}\) & A group satisfies \(gcd(b,N)=1\), where \(b\in[N-1]\) \\ \(\mathcal{F}=\mathbb{Z}_{q}^{m\times d}\) & The set of all \(m\times d\) matrices over \(\mathbb{Z}_{q}\) \\ \(\mathbb{G}=(g)\) & The cyclic group with generator \(g\) \\ \(\Phi_{m}(X)\) & The \(m\)-th cyclotomic polynomial, where \(\Phi_{m}(X)=X^{N}+1\) \\ \(R:=\mathbb{Z}[X]/\Phi_{m}(X)\) & The ring of integer polynomials modulo \(\Phi_{m}\) \\ \(R_{p}\) & The ring \(R\) with coefficients modulo \(p\) \\ \(X\) & The discrete Gaussian distribution over the ring \\ \((pk,sk)\) & The key pair of public key and secret key \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Summary of notations.