In the Paillier cryptosystem, is there a method to judge whether an encrypted number is less than 0 (without the private key) Or, is there a cryptosystem that is both order-perserving and additive homomorphic?
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 &lt; x &lt; 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&lt;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.