Why multiple homomorphic operations on a ciphertext leaks no information about the plaintext?

Question

Scenario:

Assume I encrypt message $m$ using Paillier encryption, so I would get $c=E(m)$.

I give the identical $c$ to two different parties, parties $D$ and $E$.

• Party $D$ computes: $c_{D}= E(m)^{h_1}=E(m \cdot h_1)$

• Party $E$ computes: $c_{E}= E(m)^{h_2}=E(m \cdot h_2)$

Values $c, c_{D}$ and $c_{E}$ are given to a malicious server.

---

Question: Does the server learn anything about values $m,h_1$ or $h_2$? if yes/no why?

---

Remark 1: It seems to me it cannot learn anything about the messages, because given $c$ it can do homomorphic operation on its own to get the ciphertexts $c_{D}$ and $c_{E}$; and if it could the homomorphic encryptions would not be secure anymore. But, the problem is that we have not changed the random value $r$ (in encryption) so all ciphetexts possess the identical random value.

Remark 2: I mentioned Paillier because I'm using it right now, and the question can be generalized for any homomorphic encryptions.

Answer 1

If the parties do exactly what you have described, then yes, the malicious server can learn some information. In particular, if $h_1 == h_2$, then $c_D == c_E$. So, given the $c$ values, the malicious server can learn whether or not $h_1 == h_2$. Furthermore, the malicious server can learn if either $h$ value is $1$, as $c$ would not change. Finally, if the $h$ values are drawn from a small set of numbers, where the set is known to the malicious server, the malicious server can actually brute-force the $h$ values given the $c$ values.

This is all due to the fact that homomorphically multiplying by a constant (which is done via exponentiation in the ciphertext domain) with Paillier is deterministic. Given the same ciphertext value and the same constant, you will get the same result.

To fix this issue, you should homomorphically add a fresh encryption of $0$ to the ciphertext after any operations. This rerandomization step* is very important when using Paillier or other additively homomorphic ciphers.

_{^{* Sorry to link to my own project on this, but it illustrates the point, I think.}}