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?

Improve this question
$\endgroup$
7
  • $\begingroup$ To do the homomorphic operation, all encryption must be with the same public key. $\endgroup$
    – mikeazo
    Apr 26, 2015 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, 2015 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, 2015 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, 2015 at 8:27
  • $\begingroup$ Okay, I figured you had the public key and the randomness mixed up. $\endgroup$
    – mikeazo
    Apr 27, 2015 at 10:02

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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, 2015 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, 2015 at 14:13

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.