2
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – SEJPM
    Sep 8, 2018 at 20:34
  • $\begingroup$ 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? $\endgroup$
    – mikeazo
    Sep 10, 2018 at 13:29
  • $\begingroup$ 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). $\endgroup$
    – SEJPM
    Sep 10, 2018 at 15:40
  • $\begingroup$ You may also want to look at this question (and especially the not accepted answer). $\endgroup$
    – SEJPM
    Sep 10, 2018 at 15:41
  • $\begingroup$ Thank you! I understand that it is not possible to calculate the mean. $\endgroup$
    – mip
    Sep 10, 2018 at 18:22

2 Answers 2

Reset to default
1
$\begingroup$

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!

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ It's not for practical applications $\endgroup$
    – mip
    Sep 11, 2018 at 5:51
  • $\begingroup$ @MPlesa: then why doesn't the identity function meet your requirements? $\endgroup$
    – poncho
    Sep 12, 2018 at 10:29
  • $\begingroup$ 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). $\endgroup$
    – mip
    Sep 12, 2018 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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