# Paillier cryptosystem preserve ordering of sums for two integer sequences

According to Paillier cryptosystem the product of two ciphertexts will decrypt to the sum of their corresponding plaintexts.

I have two separate integer sequences X and Y that have same number of values. I want to calculate the 1-1 combination that minimizes the sum (e.g, x1+y1 IF and ONLY IF x1+y1 <= x2+y2 AND x1+y1 <= x3+y3)

Original Data:

X: {x1,x2,x3}
Y: {y1,y2,y3}


I then Paillier encrypt the X sequence with public key r1 and the Y sequence with public key r2.

Encrypted Data:

X: {E(x1),E(x2),E(x3)} (with public key r1)
Y: {E(y1),E(y2),E(y3)} (with public key r2)


If E(x) the cyphertext for message x, then I can calculate E(x1)E(y1), E(x2)E(y2),E(x3)E(y3), decrypt them and then get the correct minimum result x1+x2.

If indeed x1+y1 <= x2+y2 AND x1+y1 <= x3+y3 does the Pailler encryption guarantees that also E(x1)E(y1) <= E(x2)E(y2) AND E(x1)E(y1) <= E(x3)E(y3). My intuition is that NO, because that would also mean that if x<y then E(x)<E(y) for the same r.

Is my understanding correct, that Paillier cryptosystem despite its homomorphic properties cannot preserve ordering of sums for the two sets X and Y when X set is encrypted by r1 and Y set is encrypted by r2? Is there any other cryptosystem that can support this?

• To do the homomorphic operation, all encryption must be with the same public key. – mikeazo Apr 26 '15 at 18:55
• @mikeazo. In its original implementation, r is not the same for different x. Look in the example here: e-voting.bfh.ch/app/download/4931760061/… But even with different r, "the product of two ciphertexts will decrypt to the sum of their corresponding plaintexts." – Alexandros Apr 27 '15 at 3:09
• @Alexandros The great about Paillier cryptosystem is the fact that users can encrypt with different randomness under the same public key that will decrypt to the correct plaintext under the single decryption key because $r^{N\lambda}=1 , \forall r \in \mathbb{Z}_{N^*}$ – curious Apr 27 '15 at 7:56
• @curious. If I use the same r for all sequences a) Would that make the cryptosystem easier to crack b) Would the ordering of the sums be preserved => min(E(x)E(y)) -> min (x+y)? – Alexandros Apr 27 '15 at 8:27
• Okay, I figured you had the public key and the randomness mixed up. – mikeazo Apr 27 '15 at 10:02

Paillier is not order preserving, so in your algorithm $x_1+y_1$ IF and ONLY IF $x_1+y_1 <= x_2+y_2 \dots$ simply does not work. You can't do the $\leq$ comparison.
Whether you have the same $r$ or not does not really matter, if we look at the encryption:
$E(m)= g^m r^n$ mod $n^2$
You could try to achieve that by fixing $r^n$ such that the product with $x$ doesn't surpass $n^2$ (and thus isn't reduced any further by the modulus), but that means you have to find $r$ so that $r^n$ is quite low, and then your entire security will go down in flames most likely.