Paillier cryptosystem, small integers and range of values

Question

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.

Answer 1

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.

Answer 2

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.