# Additively homomorphic cryptosystem with non-interactive zero-knowledge proof of non-negativity

I need a cryptosystem that is additively homomorphic. Paillier preferably, but not neccessarily.

Also, for every ciphertext the private key holder must be able to prove non-interactively that the plaintext was non-negative.

In Paillier it is rather simple to prove that the ciphertext is equal to the plaintext. The encrypting party must simply reveal the random salt. Now I need to prove that the plaintext is non-negative without revealing it.

Let's say the most significant bit of the plaintext denotes the sign.

My first flawed idea: The verifier takes the ciphertext. Let's say the plaintext had at most N bits. The verifier homomorphicaly adds 1, then floor-divides by 2, then adds 1, then floor-divides by 2, ... and so on. After N cycles positive numbers will yield 1 while negative 0. The prover now has to prove that the resulting number is 0 or 1, which can be done by revealing salt. The whole procedure is deterministic (given the salt for encrypting 1s was deterministic), that means the prover may calculate the encrypted form of 0 or 1 in advance. The resulting salt would only be needed to be attached to the ciphertext as certificate. The flaw is of course that the verifier can not floor-divide by 2, as this requires calculating of square root modulo n=pq, where p and q are unknown.

My second flawed idea: It's the prover who does the square root. He can do it, as he has the key. The certificate would consist of the series of N numbers, each equal to the square root of the previous multiplied by encrypted 1. At the end, we get 0 or 1 and we reveal the salt. The flaw is that only even numbers' encryptions can be squared. For odd numbers we would need to publish two numbers whose plaintexts differ by 1. This obviously reveals every bit of the plaintext in every step, so it's bad.

Are there any cryptosystems that can do it?

• Also, this sounds suspiciously like an XY problem. ​ ​ ​ ​ – user991 Jan 1 '16 at 5:43
• For equality, revealing the "random salt" is not "zero-knowledge". See this question for more on equality. To you, what does "negative" mean? In Paillier we are working in $\mathbb{Z}_n$. So every "negative" number can be represented by a "positive" number and vice-versa. So you'll have to explain better what you mean. – mikeazo Jan 1 '16 at 23:11
• A protocol at "4.2 Some Auxiliary Protocols" of Damgard and Jurik "A Generalisation, a Simplification and some Applications of Paillier’s Probabilistic Public-Key System" could replace revealing the salt. brics.dk/RS/00/45/BRICS-RS-00-45.pdf – Vadym Fedyukovych Jan 2 '16 at 19:56
• One would state a relation over integers (not over a ring of residues) to express "non-negative" property. One would commit an integer with a group of a hidden (unknown to Prover) order; order of multiplicative subgroup with easy logarithm (Paillier scheme) is known. – Vadym Fedyukovych Jan 3 '16 at 9:23