Paillier Homomorphic encryption to calculate the means

Question

Paillier Homomorphic encryption supports addition and multiplication with plaintext value.

Can I use these properties to calculate the means of cipher-text values? I try to use the following steps:

1. Multiply set of cipher texts (to get there sum in plaintext value)

2. Raise the calculated ciphertext in step1 to the power of $\dfrac{1}{c}$ where $c$ is the number of cipher texts) to get the average

The problem I have is that, paillier is defined in integer domain $\mathbb{Z}$ thus $\dfrac{1}{c}$ is always $0$ so the final results is also $0$.

Any help or suggestion?

Answer 1

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}$.

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$.

Answer 2

The problem I have is that, paillier is defined in integer domain $\mathbb Z$ thus $\frac1c$ is always 0 so the final results is also 0.

You are trying to use real-valued arithmetic here. You are in the wrong field for that. If you are using Paillier Encryption you work in $\mathbb Z_n^*$. The basic operations addition, subtraction, multiplication and division work differently there.

You can compute eg $\operatorname{Enc}(\frac{a+b}2)$ given $\operatorname{Enc}(a)$ and $\operatorname{Enc}(b)$, but this is not $\operatorname{Enc}(2.5)$ for $a=2,b=3$, it is the arithmetic average using the operations for $\mathbb Z_n$, ie the operations that work with a reduction $\bmod n$ after each operation and where division by $a$ works by finding $x$ such that $ax\equiv 1\bmod n$ and then multiplying by $x$.