First, this a different take on my previous question: Pailler encryption of small integers to 32-bit integers

I have to encode small integers (range 0-50) using the Paillier cryptosystem. Those values will be encountered many times (100,000) in my dataset.

Version 1

I encode each of this 51 numbers with different r and therefore I get 51 different ciphertexts. The advantage of this method is that each time any ciphertexts are multiplied, e.g., MOD(c(1)*c(2),n2) I always get the same product.

The attacker knows that the range is small (<100) but looking at the 51 different ciphertext values, he can now guess that the range is 0-50 (0 is necessarily the smallest value). Does this make possible for him to actually get the plain texts from the ciphertexts?

Version 2

For each time one of these numbers are encountered in my dataset, I use different r. Therefore I now have 100,000*51 ciphertexts. Now it is impossible for the attacker to actually get the plain texts from the ciphertexts. But the problem is that each time any ciphertexts are multiplied MOD(c(1)*c(2),n2) I do not always get the same product [the plain texts 1 and 2 are encoded multiple times with different ciphertexts], although those different products will always decrypt to the same sum of plain texts.

Obviously, version 2 is more secure. But I would rather use version 1 for its simplicity and easier processing. Does the limited range of the values, makes cracking the Paillier cryptosystem easier?

Version 3

Let's put an intermediate version. For each value in [0,50] I use up to 10 (or more) different random values of r per value. Meaning that for plain text 0, I will get up to 10 ciphertexts. Overall, 51 plain texts => 510 ciphertexts. This should somehow limit the problems of version 1, without blowing up entirely.

  • $\begingroup$ In version 1, how do you choose the 51 different $r$ values? When a new entry is added to the database, you'd have to look up the right $r$ value, meaning it is stored somewhere or computed in a deterministic fashion. $\endgroup$ – mikeazo Sep 29 '15 at 16:43
  • $\begingroup$ @mikeazo r was chosen in random (51 times) and is not stored on the DB. For the multiplications, the DB only need to know nsquare and not r. $\endgroup$ – Alexandros Sep 29 '15 at 16:45
  • $\begingroup$ So no data is ever added to the DB? Once it is encrypted, you don't have to ever use the same $r$ again to add another entry? $\endgroup$ – mikeazo Sep 29 '15 at 16:49
  • $\begingroup$ @mikeazo The data will be read only, after all data inserted on the DB. There will be no more entries added later. $\endgroup$ – Alexandros Sep 29 '15 at 16:51

With version 1, you are essentially using an additively homomorphic substitution cipher. I understand that the database is quite large, but the number of different values small. This (typically) means that statistical analysis can be used to derive a lot of information, especially if the attacker has some auxiliary information which is often the case. This is a very bad idea.

Version 3 is like version 1, but it's a bit harder to do the statistics. The problem is that the database is so big, that this may also be easy. Of course, it's very hard for me to judge how easy it is to do statistics without knowing the application and without knowing what auxiliary information is available.

Having said the above, your actual question is whether it helps the attacker to actually decrypt (say, with no auxiliary information whatsoever). The answer is no. In order to see why this is the case, consider a game whereby the attacker either receives encryptions of 0 to 50, or 51 encryptions of 0. It is easy to see that the adversary can guess which is the case with probability only negligibly greater than 1/2 (e.g., this is the multiple encryption experiment). Now, an adversary in this game can emulate the database assuming it has encryptions of 0 to 50 and can see what the adversary for the database can learn. If it can learn something, then it must be that the encryption adversary received encryptions of 0 to 50 (since encryptions of zeroes only reveals nothing).

In any case, please do not interpret the above as "approval" for version 1. I think that it's a VERY BAD idea, and strongly advocate for version 2.

  • $\begingroup$ Already upvoted your answer. Any comment on the third version? $\endgroup$ – Alexandros Sep 29 '15 at 18:03
  • $\begingroup$ Have added paragraph on version 3; for some reason I didn't see it at first. $\endgroup$ – Yehuda Lindell Sep 29 '15 at 18:17

Does the limited range of the values, makes cracking the Paillier cryptosystem easier?

That depends. I'm assuming that you are generating good, large random $r$ values, just reusing them for the same plaintexts. The main problem with this is that you loose semantic security. It however does not lead to a key leakage attack (AFAIK).

So, your question is really, given my application, does not having semantic security create security issues? That we cannot answer, as we do not know your application.

There are plenty of applications where this would be a problem. For example, let's say I have read-only database access and the encrypted field stores ages. I want to know Sally's age. So, I find everyone with the same encrypted value as Sally. Say one of them is Bob. I go ask Bob his age. Once he tells me, I now know Sally's age.

If the distribution of plaintexts is anything other than uniform, the attacker can use this to make good guesses about which ciphertexts correspond to which plaintexts by doing frequency analysis.

There may be a set of applications where semantic security is not an issue. Your application may be one of them. But what happens when the scope of your application changes and now semantic security is an issue?

Better to design for the future (or the unknown present) and go with version 2.

  • $\begingroup$ +1. Any comment on the third version? $\endgroup$ – Alexandros Sep 29 '15 at 18:03
  • $\begingroup$ For provable security, version 3 may be just as hard to prove as version 1. Version 2 is the easiest to prove security. $\endgroup$ – mikeazo Sep 29 '15 at 18:07

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.