3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ To do the homomorphic operation, all encryption must be with the same public key. $\endgroup$ – mikeazo Apr 26 '15 at 18:55
  • $\begingroup$ @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." $\endgroup$ – Alexandros Apr 27 '15 at 3:09
  • $\begingroup$ @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^*}$ $\endgroup$ – curious Apr 27 '15 at 7:56
  • $\begingroup$ @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)? $\endgroup$ – Alexandros Apr 27 '15 at 8:27
  • $\begingroup$ Okay, I figured you had the public key and the randomness mixed up. $\endgroup$ – mikeazo Apr 27 '15 at 10:02
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. I needed someone to confirm this. Already upvoted. I will wait a little while before accepting your answer, in case someone else answers too. $\endgroup$ – Alexandros Apr 27 '15 at 12:10
  • 1
    $\begingroup$ If you consider exchanging the encryption scheme, I would recommend to read the paper Conjunctive, Subset, and Range Queries on Encrypted Data from Boneh and Waters (2007). As keywords for further research: range query, searchable encryption, order preserving encryption, set membership, range proof, ... $\endgroup$ – tylo Apr 27 '15 at 14:13

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.