# Paillier Homomorphic encryption to calculate the means

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?

• Possible duplicate of crypto.stackexchange.com/questions/2076/…. Is there anything about your question that is not answered there? – mikeazo Nov 18 '17 at 13:25
• To get the "usual" meaning of average, you'd need floating / fixed point arithmetic and no standard crypto primitive has a homomorphism for them. – SEJPM Nov 18 '17 at 15:57
• Thank you for replay. I try to use the same basic idea as in PulpSpy's answer in crypto.stackexchange.com/questions/2076/… but the main challenge I have how to raise the double $b^-1$ to power of bigInteger $ciphertext$ when I calculate $E(a)^b^-1$ in java – Karen Nov 18 '17 at 18:00
• Is your question just how to do it in Java? If so, that is off-topic for this site. – mikeazo Nov 18 '17 at 18:29
• the focus on how to allow mean calculation over the paillier cipher texts. Any suggestion need to be practical (could implement in java). – Karen Nov 18 '17 at 18:32

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

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

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

• I hope this clears the main confusion, if anything is left unclear, ask! – SEJPM Nov 18 '17 at 21:22
• To emphesize the point that SEJPM was making, you could compute $\operatorname{Enc}(\frac{a+b}2)$, however, the $/2$ part doesn't mean what you expect; if $a=0$ and $b=1$, then $\operatorname{Enc}(\frac{a+b}2) = \operatorname{Enc}((n+1)/2)$, which is probably not what you're looking for... – poncho Nov 18 '17 at 22:10