# Commitment which allows negative proof

I need to create a commitment to a value X such that I can provide either proof that the commitment is to X or proof that the commitment is not to some other given value Y != X.

If I use a simple hash with a blinding factor

C = H(BF | X)


I can provide proof by revealing BF,X and "negative proof" that X!=Y by revealing BF, but this would defeat the purpose of the blinding factor, making X guessable as it has a small domain.

Is there some other way to create such commitment?

• BTW: in your example, just revealing BF wouldn't actually be a proof of commitment to some other value, as you don't give a proof that the value you send isn't just a random value. One could construct such a proof, but it would be a pain... Jan 24, 2019 at 15:43
• Yes. I understand that if you want to reveal the BF, you need to include it in the commitment, e.g. C = H(BF | H(BF | X)) Jan 25, 2019 at 10:45

The immediately obvious idea is to use Pedersen commitments. The idea here is that, in some group where the DLog problem is hard, we have two generators of unknown relation $$g, h$$, and a commitment to $$x$$ is the value $$g^x h^r$$ (for some random $$r$$).

To reveal the commitment is easy; you just give the values $$x, r$$ (and the verifier can check).

To prove that a value $$x'$$ is not the committed value to a commitment $$g^x h^r$$, the prover selects random values $$s, t$$, and publishes the value $$h^t$$, along with a zero knowledge proof that he knows the dlog of $$h^t$$ to the base $$h$$ (a standard cut-and-choose proof works). Then, both sides compute $$g^{-x'} h^t (g^x h^r) = g^{x - x'} h^{r+t}$$, which we will call $$j$$. Now, the prover computes $$j^s = g^{s(x-x')} h^{s(r+t)}$$, and outputs that, along with the values $$s(x-x')$$, $$s(r+t)$$. He also outputs a zero knowledge proof that he knows the discrete log of $$j^s$$ to the base $$j$$.

The verifier can check that $$s(x-x') \ne 0$$, that the values $$s(x-x')$$, $$s(r+t)$$ make up the outputted value $$j^s$$, and that the proofs of knowledge of $$s, t$$ are valid.

Then, the verifier knows that the prover knows the value $$s(x - x')$$ and that it's not zero, hence $$x - x' \ne 0$$ and so whatever $$x$$ is, it ain't $$x'$$

There are also standard range techniques that would also work; I believe that this is more straight-forward...

• Thank. That makes sense. As for proof that he knows the dlog of h^t, j^s. What's a cut-and-choose proof? My knowledge is limited, but wouldn't a (DSA) signature work for that? Jan 25, 2019 at 10:50
• @Tomas: to prove that, given $h, h^t$, you know $t$, what the prover does is generate a random $u$ and publish $h^u$. Then, the verifier picks a bit $b$; if $b=0$, then the prover publishes $u$ (and the verifier can check that); if $b=1$, then the prover publishes $u^{-1}t$ (and the verifier can check that $(h^t) = (h^u)^{(u^{-1}t)}$. We do this with a series of random $u, b$ values; if the prover doesn't know $t$, the probability of success after $n$ iterations is at best $2^{-n}$. This is zero knowledge, in the sense that the verifier learns nothing else... Jan 25, 2019 at 14:38