1

Given a value $v = g^ah^b$, with $a,b$ secret, I was wondering whether there was a way to prove in zero knowledge that neither exponent is zero. In other words, given $v$ and $g,h \in \mathbb{G}$, I want to prove $\{a,b \in \mathbb{Z}_p: v = g^ah^b\wedge a\neq 0 \wedge b \neq 0\}$. I know how to achieve the first condition, but I do not know how to achieve the other two.

I know sigma protocols are generally used for this types of proofs, but I haven't found one that achieves specifically this.

Edit:

I should add that $g^a$ and $h^b$ cannot be revealed to the Verifier in my case.

Edit 2:

To achieve the first condition (knowledge of $a,b$ such that $v = g^ah^b)$:

Prover

$r_1, r_2 \in \mathbb{Z}_p$

$u = g^{r_1}h^{r_2}$

$c = H(g, h, u, v)$

$z_1 = r_1 + ca$

$z_2 = r_2 + cb$

Send $(u, c, z_1, z_2)$ to Verifier.

Verifier

$c \stackrel{?}{=} H(g, h, u, v)$

$g^{z_1}h^{z_2} \stackrel{?}{=} v^cu$

John N.
  • 23
  • 4
  • What is your method of achieving the first condition? – knaccc Jun 18 '22 at 18:52
  • I edited the question to add the sigma protocol I use for the first condition. – John N. Jun 18 '22 at 19:11
  • Your proof of the first condition looks good to me. Note that you do not need to communicate $c$ to the verifier, since they can calculate it themselves. – knaccc Jun 18 '22 at 20:03

1 Answers1

1

Your Pedersen commitment $v$ can either be considered a commitment to the value $a$ with blinding factor $b$, or as a commitment to value $b$ with blinding factor $a$.

Let $\ell$ be the group size of your generators $g$ and $h$.

Without loss of generality, you can use a range proof to demonstrate that $v$ is a commitment to a value $a$ such that $0<a<\ell$. You then create a similar range proof, treating $v$ as a commitment to the value $b$, and prove that $0<b<\ell$.

To prove that $0<a<\ell$, calculate the commitment $v'=v/g$ and prove that $v'$ is a commitment to the value $a'$ such that $0\leq a'<\ell-1$.

The range proof demonstrates that $v'$ can be a constructed from a list of components which together cannot equal or exceed the upper bound $\ell-1$.

To calculate the component values, see this answer.

To see how to construct the range proof using those components, see this answer.

knaccc
  • 4,732
  • 1
  • 16
  • 30
  • Thank you for your answer! I have a question related to your answer. Is proving $0 < a < l$ more or equally as expensive than proving $0 \leq a < l$? – John N. Jun 19 '22 at 13:38
  • @JohnN. The range proof mechanisms I'm personally familiar with can only directly check an upper bound, which is why if the lower bound is non-zero, the $x<a<y$ check is first converted to the equivalent $0\leq (a-x)<(y-x)$ check. The cost of this conversion is not significant compared to the overall calculations required to create/verify the proof. – knaccc Jun 19 '22 at 16:59