# 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... – poncho Jan 24 '19 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)) – Tomas Jan 25 '19 at 10:45

## 1 Answer

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? – Tomas Jan 25 '19 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... – poncho Jan 25 '19 at 14:38