# Zero knowledge proof of a linear expression in the exponent

Alice sends to Bob a value $$B$$ in $$\mathbb{G}$$ a group of high order. There are distinct elements $$h_1$$ and $$h_2$$ of high order of $$\mathbb{G}$$, and Alice wants to prove to Bob that she knows some values $$b_1, b_2 \in \mathbb{Z}_q$$ such that $$B=h_1^{b_1}h_2^{b_2}$$.

I have found the following related post (quite old and without answer), but I could not find any information about the mentioned Okamoto protocol.

1/ Is this kind of proof possible and what are the techniques used in the literature to construct such a zero knowledge proof of knowledge?

2/ Is the Okamoto protocol in the related post correct? Where can we find information about it?

• What research have you done? What have you found and tried? Apr 12 at 20:03
• @e-sushi I am not aware about the techniques we could use. Some pointers, courses, videos, could help Apr 12 at 21:49
• Note: If I understand the question correctly, it's about Zero knowledge proof of knowledge of coefficients in a linear expression. The term linear becomes clearer is we rewrite the expression $B=h_1^{b_1}h_2^{b_2}$ with the group $\mathbb G$ noted additively rather than multiplicatively. The problem then is proving knowledge of scalars $b_1$ and $b_2$ such that $B=b_1\cdot H_1+b_2\cdot H_2$, without disclosing anything about these $b_1$ and $b_2$. (continued)
– fgrieu
May 12 at 7:57
• With that additive notation, the protocol proposed in the related post is: Prover picks random secret $r_1,r_2\in\mathbb Z_q$, sends $A=r_1\cdot H_1+r_2\cdot H_2$. Verifier picks and sends random $c\in\mathbb Z_q$. Prover computes and sends $z_1=r_1+c\,b_1\bmod q$, $z_2=r_2+c\,b_2\bmod q$. Verifier checks that $z_1\cdot H_1+z_2\cdot H_2=A+c\cdot B$, and if that holds accepts that prover knows $b_1$ and $b_2$. I'm not able to answer the question (in particular I fail to decide if this proof is "zero-knowledge").
– fgrieu
May 12 at 8:49
• Thank you @fgrieu May 15 at 7:26