## 2 Preliminaries  
### Multiparty Homomorphic Encryption  
In this paper, we utilize the Cheon-Kim-Kim-Song [16] variant of the MHE scheme presented in Ref. [17], which enables secure computations to be performed over \"real\" numbers. Under this scheme, ciphertexts are encrypted under a public key with the corresponding secret key being held in a distributed manner amongst the parties. Therefore, decryption is an interactive process with each party performing some partial decryption, which is combined in the end to result in the plaintext. Additionally, the MHE scheme admits a collective bootstrapping protocol that is much more computationally efficient than standard bootstrapping techniques for the non-multiparty CKKS scheme.  
Figure 1: Federated analytics system architecture.  
The plaintext space is \(R_{Q_{L}}=\mathbb{Z}[X]_{Q_{L}}/X^{\mathcal{N}}+1\) where \(Q_{L}=\prod_{i=1}^{L}q_{i}\) for \(q_{i}\) prime, \(\mathcal{N}\) is a power of 2 and \(L\) represents the number of levels or the number of multiplications allowed before the noise in the ciphertext must be refreshed. The ciphertext space is consequently \(R_{Q_{L}}^{2}\). Under this scheme, \(\frac{\mathcal{N}}{2}\) values can be packed into a single ciphertext. The following functions are permitted in the CKKS variant of the MHE scheme:  
* **SecKeyGen(1):** Each party \(P_{i}\) generates its own secret key \(sk_{i}\) with security parameter \(\lambda\);
* **ColKeyGen(\(\{sk_{i}\}\)):** The parties collectively generate the collective public key \(pk\);
* **Encode(v):** Encodes a vector of complex numbers \(\mathbf{v}\in\mathbb{C}^{\mathcal{N}/2}\) as a plaintext \(\hat{p}\in R_{Q_{L}}\);
* **Decode(\(\hat{p}\)):** Decodes a plaintext \(\hat{p}\in R_{Q_{L}}\) into a vector of complex numbers \(\mathbf{v}\in\mathbb{C}^{\mathcal{N}/2}\);
* **Encrypt(\(pk\), \(\hat{p}\)):** Encrypts plaintext \(\hat{p}\in R_{Q_{L}}\) to ciphertext \(\hat{c}\in R_{Q_{L}}^{2}\) under the public key \(pk\);
* **ColDecrypt(\(\hat{c}\), \(\{sk_{i}\}\)):** The parties collectively decrypt a ciphertext \(\hat{c}\in R_{Q_{L}}^{2}\) into a plaintext \(\hat{p}\in R_{Q_{L}}\);
* **ColBootstrap(\(\hat{c}\), \(\{sk_{i}\}\)):** The parties collectively refresh the noise in the ciphertext \(\hat{c}\in R_{Q_{L}}^{2}\) returning a new ciphertext \(\hat{c}^{\prime}\in R_{Q_{L}}^{2}\) with less noise;
* **HAdd(\(\hat{c}\), \(\hat{c}^{\prime}\)):** Adds 2 ciphertexts \(\hat{c},\hat{c}^{\prime}\in R_{Q_{L}}^{2}\);
* **HSub(\(\hat{c}\), \(\hat{c}^{\prime}\)):** Subtracts the second ciphertext \(\hat{c}^{\prime}\) from the first \(\hat{c}\);
* **HMul(\(\hat{c}\), \(\hat{c}^{\prime}\)):** Multiplies 2 ciphertexts \(\hat{c},\hat{c}^{\prime}\in R_{Q_{L}}^{2}\);
* **HRotate(\(\hat{c}\), \(k\)):** Assuming \(\hat{c}\) encodes and encrypts \([v_{1},\ldots,v_{d}]\), returns a ciphertext \(\hat{c}^{\prime}\) encoding and encrypting \([v_{k},\ldots,v_{d},v_{1},\ldots,v_{k-1}]\);
* **HInnerSum(\(c\)):** For a ciphertext \(\hat{c}\in R_{Q_{L}}^{2}\) which encodes and encrypts a vector \(\mathbf{v}\in\mathbb{C}^{\mathcal{N}/2}\), compute the ciphertext that encodes and encrypts the vector \(\mathbf{v}^{\prime}\in\mathbb{C}^{\mathcal{N}/2}\) which has, as all its elements, the \(L_{1}\) norm of the vector \(\mathbf{v}\) i.e., \(\mathbf{v}^{\prime}\approx||\mathbf{v}||_{1}\cdot\mathbf{1}\).  
Note that while technically the HAdd, HSub, and HMul operations have been defined here to operate on two ciphertexts, we abuse the notation in this paper to allow the second argument to be a plaintext (HAdd(\(\hat{c}\), \(\hat{p}\))) or a constant (HAdd(\(\hat{c}\), \(a\))).