4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.