# Privacy-Preserving Federated Learning Using Homomorphic Encryption
## 3 Preliminary
### Distributed Homomorphic Cryptosystem  
Distributed homomorphic cryptosystem (DHC) is a cryptosystem that can perform various homomorphic operations using secure multiparty computation (SMC) for implementing various homomorphic operations in a distributed manner. Figure 1 illustrates the decryption process of DHC. In typical public-key cryptography, parties with public and private keys perform encryption and decryption for secure communication, respectively. On the other hand, a private key is divided into several partial private keys in the DHC, and the partial private keys are distributed to multiple distributed servers. Distributed servers with partial private keys perform partial decryption using values encrypted with the public key. The other distributed server can obtain the plaintext by collecting the partially decrypted ciphertexts. This decryption process enables a variety of homomorphic operations based on multilateral cooperation.  
The functions for the DHC are described as follows:  
* **Key generation**: Function that generates a public-private key pair \((pk_{i},sk_{i})\), \(i\in\{1,\cdots,N_{c}\}\) of a user for given two large prime numbers \(p\) and \(q\), where \(N_{c}\) is the number of clients participating in the local training.The public key is calculated by \(p\cdot q\), and the private key corresponding to the public key is calculated by \(lcm(p-1,q-1)/2\), where \(lcm(x,y)\) denotes the least common multiple (LCM) of x and y. Note that the key size \(K\) is \(p\cdot q\). Then, as the selected prime numbers increase, the computational complexity of cryptosystem increases because the complexity for the exponentiation operation of encryption and decryption increases [22]. Then, partially private keys\([psk_{i}^{(1)},psk_{i}^{(2)},\cdots,psk_{i}^{(N_{s})}]\) for distributed servers can be obtained by splitting the private key \(sk_{i}\), where \(N_{s}\) is the number of distributed servers [23]. We select \(\delta\) that satisfies \(\delta\equiv 0\bmod sk_{i}\) and \(\delta\equiv 1\bmod K^{2}\) at the same time and select \(y\) random numbers \(\{a_{1},a_{2},\ldots,a_{y}\}\) from \(\mathbb{Z}_{sk_{i}k^{2}}^{*}\). Then, we use these values to define the polynomial \(p(x)=\delta+\sum_{i=1}^{y}a_{i}x^{i}\). The partial private key \(psk_{i}^{(j)}\) is obtained by calculating the polynomial \(p(x_{j})\) using a non-zero value \(x_{j}\) from \(\mathbb{Z}_{sk_{i}k^{2}}^{*}\).
* **Encryption**: Function that generates a ciphertext \(Ep_{k_{i}}(m)\in\mathbb{Z}_{k^{2}}^{*}\) for a plaintext \(m\in\mathbb{Z}_{K}\), using a public key \(pk_{i}\), where the key size \(K\) is \(p\cdot q\). For simplicity, the ciphertext \(Ep_{k_{i}}(m)\) can be represented by \([m]_{i}\);
* **Decryption**: Function that decrypts a ciphertext \([m]_{i}\) using a private key \(sk_{i}\) and returns \(m\);
* **Partial decryption**: Function that generates a partially decrypted ciphertext by partially decrypting \([m]_{i}\) using a partial private key \(psk_{i}^{(k)}\), \(k\in\{1,\cdots,N_{s}-1\}\), as shown in Figure 1. For simplicity, the partially decrypted ciphertext \(PD_{psk_{i}^{(k)}}([m]_{i})\) can be denoted by \(PD^{k}([m]_{i})\);
* **Combined decryption**: Function that obtains and returns \(m\) using \((N_{s}-1)\) partially decrypted ciphertexts \(PD^{k}([m]_{i})\) for \(\forall k\in\{1,\cdots,N_{s}-1\}\) and the partially private key \(psk_{i}^{(N_{s})}\). Note that a vector \(\boldsymbol{PD}([m]_{i})\) signifies \([PD^{1}([m]_{i}),PD^{2}([m]_{i}),\cdots,PD^{N_{s}-1}([m]_{i})]\) in Figure 1.  
Using the DHC, we have established a PPFL-based system in which the parties can jointly perform a global model update based on homomorphic operations to preserve the data privacy of the participants in the FL training process. The proposed PPFL algorithm is explained in detail in Section 5.