The Paillier encryption of an integer $x_i$ is given by $c_i = (1+x_iN)r_i^N \bmod N^2$ for some random $0<r_i<N$. Given the encryption of $x_1, \dots, x_k$, the encrypted mean is defined as $$[\![\mu]\!] = \left(\prod_{i=1}^k c_i\right)^{k^{-1}\bmod N} r^N\bmod N^2$$ for some random $0<r<N$.
If we now apply Paillier decryption procedure to $[\![\mu]\!]$, we get $$\mu = \frac{\sum_{i=1}^k x_i}{k} \bmod N$$ We assume $\sum_{i=1}^k x_i< \sqrt{N}$. Now an application of Lagrange-Gauss lattice-reduction algorithm yields $\mu$ as an element in $\mathbb{Q}$.
[FSW02] Pierre-Alain Fouque, Jacques Stern, and Jan-Geert Wackers. Cryptocomputing with rationals. In Financial Cryptography, volume 2357 of Lecture Notes in Computer Science, pages 136–146. Springer, 2002.Based on: [FSW02] Pierre-Alain Fouque, Jacques Stern, and Jan-Geert Wackers. Cryptocomputing with rationals. In Financial Cryptography, volume 2357 of Lecture Notes in Computer Science, pages 136–146. Springer, 2002.
Alternatively, instead of using Lagrange-Gauss algorithm, we can adapt the extended Euclidean algorithm:
[u1, u2] = [0, N]; [v1, v2] = [1, mu];
while (u2 > sqrt(N)) do
Q = u2 div v2; [t1, t2] = [u1, u2] - [v1, v2]*Q;
[u1, u2] = [v1, v2]; [v1, v2] = [t1, t2];
endwhile
return u2/u1
Here is a toy example with $p = 739$, $q = 839$, and $N = pq = 620021$. Suppose $x_1 = 97$, $x_2 = 74$ and $x_3 = 46$.
We are given their respective encryptions: $c_1 = 206197787317$, $c_2 = 267770082390$, and $c_3 = 49804921902$. We have $k=3$ and $k^{-1} \bmod N = 206674$. We choose a random $r<N$, say $r = 559196$ and compute $$[\![ \mu]\!] = (c_1c_2c_3)^{k^{-1}\bmod N} \, r^N \bmod N^2 = 127639014845$$
The decryption of $[\![\mu]\!]$ yields $\mu = 206746 \pmod N$. Lagrange-Gauss algorithm then yields $206746 \equiv \frac{217}3 \pmod N$ and thus $\mu = 217/3 = 72.33$.
