In Paillier cryptoststem many ciphertexts can correspond to the same plaintext. How can I modify the scheme so to make the correspondence between ciphertexts and plaintexts a one to one correspondece? I've already eliminated the randomness from the scheme (i.e. all encryptions are done with the same $r$).

My reason for this is that I want to compute the arithmetic mean of two encrypted numbers by repeatedly subtracting 2 (which I can do no-problem) until I hit 0 which I then need to detect.

  • You may want to have a look at section 5.2 of this paper (PDF) which has a zero-knowledge proof (without the need for derandomization and access to the private key) to show somebody that 0 was encrypted under the given scheme which is a generalization of Paillier. – SEJPM Sep 8 at 20:34
  • I don't understand what your question is. You've fixed $r$ to a static value. Doesn't that get you what you want? If not, why? – mikeazo Sep 10 at 13:29
  • Note that there is a bug in your approach, if the mean is odd, you will never actually hit an encryption of 0. Also you may want to note that Paillier allows you to multiply by constants, including $2^{-1}\bmod n$ (but which only works as you probably intended if the sum of the numbers is even). – SEJPM Sep 10 at 15:40
  • You may also want to look at this question (and especially the not accepted answer). – SEJPM Sep 10 at 15:41
  • Thank you! I understand that it is not possible to calculate the mean. – mip Sep 10 at 18:22
up vote 1 down vote accepted

The Paillier is semantically secure. So, even the same values will have different ciphertext all the time. Amount of the different ciphertext can be calculated by the input size of the random $r \leftarrow \mathbb{Z}_n^*$, $=2^n-1$.

You can add the two values semantically, and decrypt their addition since Paillier is additive homomorphic.

$$E(a+b \bmod N) = E(a) \cdot E(b) $$ I.e. the multiplication of ciphertext is equal to addition of plaintexts.

Your problem will be their average, here division by 2. This is not possible since Paillier doesn't support multiplication!

How can I modify the scheme so to make the correspondence between ciphertexts and plaintexts a one to one correspondece?

You do realize that this would make encryption insecure, don't you? After all, someone who knows what an encrypted 1 looks like can subtract 1 until he gets one; this immediately reveals what value the original ciphertext stood for.

If security is not a requirement, might I suggest using the identity function as your encryption mechanism. It is deterministic, it can be implemented quite efficiently, and for that matter, it is fully homomorphic.

  • It's not for practical applications – mip Sep 11 at 5:51
  • @MPlesa: then why doesn't the identity function meet your requirements? – poncho Sep 12 at 10:29
  • I want Paillier encryption because I want to compute the arithmetic mean of two encrypted numbers. The requirements were made in order for my algorithm to work (I now understand that this is not the way I can compute the mean). – mip Sep 12 at 11:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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