In the Paillier cryptosystem, is there a method to judge whether an encrypted number is less than 0 (without the private key)

Question

Or, is there a cryptosystem that is both order-perserving and additive homomorphic?

Answer 1

In Paillier, if it were possible to determine whether an encrypted number is less than 0 (that is, is equivalent modulo N to a value $x$ where $N/2 < x < N$), then it would be possible to decrypt arbitrary encrypted values with only the public key. That is, if someone found such a method, they will have broken Paillier as a public key system.

The details are fairly straight-forward; to compare an encrypted value $E(x)$ against a known value $y$, you compute $E(y)$, use the homomorphic property to compute the value $E(x+y)$, and then use your blockbox to determine from this value whether $x+y<0$

Hence, you can use binary searching, using the above method as the comparison method, to recover the value $x$ given $E(x)$, using $O(\log N)$ probes.

Answer 2

As mentioned above this is not possible in a direct way. However there exists a Zero Knowledge Proof that may do the job. It proofs that a message encrypts one out of a publicly known number of plain text messages. If these known messages only contain values greater or equal 0 this may be what you are looking for but unfortunately message and computation overhead is quite high for large sets.

Have a look at this pdf, page 17 "Proof that an encrypted message lies in a given set of messages".