How to prove a num less than 0?

[xuzhitong]

I want to use zk-paillier range proof to prove a secret num less or more than 0.I noticed the comment "Zero-knowledge range proof that a value x<q/3 lies in interval [0,q]." in the code.So I must design a algorithms to meet the logic:
if x < 0 then
x' < q/3
else
x' > 2q/3
My simple algorithms is as below:
if x%3 == 0
x' = 2/3q + 1/3q*(x+2)%3
else
x' = 2/3q + 1/3q*x%3
But it's too hard to verify because verifier need to verify the encrpt relationship between x and x' at first.
Is there any better way?
Any suggestion would be appreciated!

[omershlo]

Hi @xuzhitong !
first question is : did you consider using bulletproofs/++ for this range proof? even if only got Paillier ciphertext - you can make an equivalent pederson commitment and run bulletproofs.
The reason I am asking is because the range proof in this repo is a bit limiting because q must be of certain size compared to the Paillier modulus and the q/3 issue.

about the specific algorithm: since we do our computations in a field (modulo arithmetic) saying that a number is negative is actually saying that it is suppose to be in the range (-q, 0) right? in that case I suggest to wrap it (homomorphically add a ciphertext encrypting q ) and prove that the ciphertext encrypts a number in [0, q)

[xuzhitong]

Hi @xuzhitong !
first question is : did you consider using bulletproofs/++ for this range proof? even if only got Paillier ciphertext - you can make an equivalent pederson commitment and run bulletproofs.
The reason I am asking is because the range proof in this repo is a bit limiting because q must be of certain size compared to the Paillier modulus and the q/3 issue.

about the specific algorithm: since we do our computations in a field (modulo arithmetic) saying that a number is negative is actually saying that it is suppose to be in the range (-q, 0) right? in that case I suggest to wrap it (homomorphically add a ciphertext encrypting q ) and prove that the ciphertext encrypts a number in [0, q)

Thanks for your reply!
Because i'm writting a simple privacy block chain system and use the account model like ethereum,so the bulletproof and pedersen committment may be not work well.for example,there are two accounts A and B,their paillier encrypted balance are stored on blockchain's contract.When A want to transfer some amount to B privately,the verifiers in the network must verify the proofs with the encrypted balance stored on the blockchain:
1.the encrypted transfer amount is more than 0
2.the encrypted balance of A homomorphically sub the encryped transfer amount is must more than 0
I think the pedersen commitment may be not fit here,so i use the zk-paillier.
I can't get the specific algorithm you suggested.Could you make it more clear?If a encryped number homomorphically add a ciphertext encrypting q ,how to prove the encryped result is in [0,q)?

[omershlo]

I hope I am not mistaken in understanding your use case. this is the algorithm I suggest:
input ciphertext c = Enc(x)
output bool true/false
steps:
encrypt: c_q = Enc(q/3)
If range_proof (c) = 1 output true
if range proof (c) = 0 and range_proof (c + c_q) = 1 output false

does that makes sense ?

[xuzhitong]

I hope I am not mistaken in understanding your use case. this is the algorithm I suggest:
input ciphertext c = Enc(x)
output bool true/false
steps:
encrypt: c_q = Enc(q/3)
If range_proof (c) = 1 output true
if range proof (c) = 0 and range_proof (c + c_q) = 1 output false

does that makes sense ?

Thanks for your reply.I still have some doubts about the implemetaion.I found the paillier encrypt function is as below:

impl<'m, 'd> Encrypt<EncryptionKey, RawPlaintext<'m>, RawCiphertext<'d>> for Paillier {
    fn encrypt(ek: &EncryptionKey, m: RawPlaintext<'m>) -> RawCiphertext<'d> {
        let r = Randomness::sample(&ek);
        let rn = BigInt::modpow(&r.0, &ek.n, &ek.nn);
        _let gm: BigInt = (m.0.borrow() as &BigInt * &ek.n + 1) % &ek.nn;_
        let c = (gm * rn) % &ek.nn;
        RawCiphertext(Cow::Owned(c))
    }
}  

I noticed the gm is equal to (m*n+1)%nn.If the raw plain text is negative,the encrypt result is negative too.So in the verifier_output,the condition is not met:

let enc_zi = Paillier::encrypt_with_chosen_randomness(
                            ek,
                            RawPlaintext::from(masked_x),
                            &Randomness::from(masked_r.clone()),
                        );
                        if &c != enc_zi.0.borrow() {
                            res = false;
                        }

Since the masked_x is not negtive,the enc_zi is not negtive.
I'm not sure if there is leaked the knownledge of the m's sign?

[xuzhitong]

I also view the code reference paper:
Appendix A in Lindell'17
I found the line :

Soundness: Let c = Encpk(x) and assume that x /∈ Zq and so in particular
x ≥ q (note that if x is negative then modulo q this is the same as x ≥ q).

Is there another way to implement the proof and verify without leaking the number's sign?

[omershlo]

Have you tested my suggest protocol ?
I think this is the best way to prove it doesn’t work as you claim

[xuzhitong]

Have you tested my suggest protocol ?
I think this is the best way to prove it doesn’t work as you claim

yes,I have tested your suggest protocal and it can works.