0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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... $\endgroup$
    – poncho
    Jan 24, 2019 at 15:43
  • $\begingroup$ 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)) $\endgroup$
    – Tomas
    Jan 25, 2019 at 10:45

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Tomas
    Jan 25, 2019 at 10:50
  • $\begingroup$ @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... $\endgroup$
    – poncho
    Jan 25, 2019 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.