# 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?

-
A fully order-preserving cryptosystem would have a few issues.. –  Thomas Jan 23 '13 at 15:46
The message space of the Paillier Cryptosystem is $\mathbb{Z}_N$. So, in fact, yes it is possible to judge that, because they never are. (But that is probably not what you actually wanted to know.) –  Maeher Jan 23 '13 at 15:59
Might be possible to have someone prove a predicate about a ciphertext if they were the one who encrypted the value to get the given ciphertext. Not sure if that meets your needs. –  mikeazo Jan 24 '13 at 0:46
Thank you all. So it seems that any order-perserving and additive homomorphic public key cryptosystem is broken, as shown by poncho... –  phan Jan 24 '13 at 1:35

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.

-
You are right. Thank you. However, is there any symmetrical encryption system that matchs this two properties? –  phan Jan 24 '13 at 1:40
@phan I don't know of any additively homomorphic symmetric ciphers, but if such a cipher existed, it would not be IND-CPA secure. The attacker could use the order property to work out which of the two ciphertexts belongs to any one plaintext. –  Thomas Jan 24 '13 at 2:08
@Thomas Yes, any order-perserving systems I know lack the semantical security, as well as any deterministic encryption schemes like AES ... Hence I think it is acceptable for some applications ... –  phan Jan 24 '13 at 2:19