# 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

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".

-
Thank you for the interesting paper! However, if what I understand is correct, this protocol can be executed for each encrypted number only few times, otherwise it serves as the binary-searching-enabling blockbox mentioned by poncho... –  phan Jan 27 '13 at 15:32
As far as I can judge this ponchos counter-example makes different assumptions. In his case the blackbox is available to anyone and does not require the cooperation of any other party. So an attacker can query the box with any input he likes. However, in case of the Zero Knowledge Proof (ZKP) the proof stringently requires cooperation of the secret-holder. The basic idea of any ZKP is that a prover applying a ZKP can never reveal more to a verifier than what he has already stated. –  Thomas Lieven Jan 29 '13 at 15:26