1
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ What is your method of achieving the first condition? $\endgroup$
    – knaccc
    Jun 18, 2022 at 18:52
  • $\begingroup$ I edited the question to add the sigma protocol I use for the first condition. $\endgroup$
    – John N.
    Jun 18, 2022 at 19:11
  • $\begingroup$ 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. $\endgroup$
    – knaccc
    Jun 18, 2022 at 20:03

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$
    – John N.
    Jun 19, 2022 at 13:38
  • $\begingroup$ @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. $\endgroup$
    – knaccc
    Jun 19, 2022 at 16:59

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.