1
$\begingroup$

Suppose I want to commit to the following information:

  • I have an integer $i\in\mathbb Z$ and I want to commit to $i$ and that $i\gneq 0$, without revealing $i$.

  • I have an element of a prime field $x\in\mathbb F_p$. I want to commit to $x$ and that it's nonzero, without revealing $x$.

Can anyone advise on the current state of the art?

My question seems to be a special case of both of these questions:

but what I take from these answers is that it's quite complicated. For instance this answer runs to multiple pages. So, I am particularly interested in simple (if not necessarily optimal) schemes.

Thank you.

$\endgroup$

1 Answer 1

1
$\begingroup$
  1. I have an element of a prime field $x\in\mathbb F_p$. I want to commit to $x$ and that it's nonzero, without revealing $x$.

Actually, that part is pretty easy (as long as $p$ is of reasonable size, say $> 2^{256}$).

First, we pick a $q = kp + 1$ prime which is at least 2048 bits long (to make the discrete log problem hard) [1].

Then, we use a Pedersen commitment of $x$, that is, we pick elements $g, h$ of the subgroup of size $p$ where $\log_g h$ is unknown, and a commitment is $C = g^xh^r \bmod q$, for a random value $r$.

To prove that, for $C$, the committed value $x \ne 0$, we select a random exponent $s \ne 0$, compute $A = C^s \bmod p$ and $B = g^{xs} \bmod p$, and publish $A, B$ along with zero knowledge proofs that:

  • We know the value $s$ for which $A = C^s$

  • We know the value $t$ for which $B = g^t$

  • We know the value $u$ for which $AB^{-1} = h^u$

These can be generated by issuing Schnorr proofs of knowledge.

To verify this zero knowledge proof, we would check that $A, B$ are in the subgroup of size $p$ (that is, $A^p = 1, B^p = 1$), that $B \ne 1$ (which implies that $t \ne 0$), and verify the three zero knowledge subproofs.

This works because the verify can see that $(g^xh^r)^s g^{-t} = h^u$, that is, $g^{xs-t}h^{rs} = h^u$. Because the prover knows the values $x, s, t, r, u$ but not the value $g^z = h$, we must have $xs-t = 0$ and $rs = u$ (otherwise the prover could reconstruct $z$). And, because $t \ne 0$, we must have $xs \ne 0$, hence $x \ne 0$.


[1]: I do this in the mod $q$ group because it is easy to construct such a group with a $p$ sized subgroup. If you happen to have an elliptic curve with such a subgroup, you can use that as well...

$\endgroup$
1
  • $\begingroup$ Very nice. Essentially, you've blinded the Pedersen commitment, in order to be able to demonstrate that it takes a semi-Pedersen commitment to a value that is not zero to cancel out the amount on G. $\endgroup$
    – knaccc
    Commented Mar 27 at 22:17

Your Answer

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

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