# Sigma protocol: witness hiding

I am working on an assignment and I am stuck with the last part of proving witness hiding for the protocol.

I have previously proved it is witness indistinguishable, and it has q (primer number chosen as in Schnorr's protocol) different values for the witness.

The protocol goes as follows: To prove the witness hiding it is hinted to show two things:

1.) if an adversary computes a valid witness (w1', w2') for a conversation it will be a different one with a high probability

I assume this is just due to that fact of witness hiding, e.g. the conversation tells noting about which of the q different witnesses was used.

2.) But if such a different pair is computed, one can compute the dsicrete log of g1 base g2.

I am pretty much stuck on this part.

I get to a point where I have an equation like this $$g_1^{w_1}\cdot g_2^{w_2} = g_1^{w'_1}\cdot g_2^{w'_2} \text{ mod p}$$

But where to go from here...

The second point is very simple: if you have $$w_1, w_2, w'_1, w'_2$$ so that $$g_1^{w_1} g_2^{w_2} = g_1^{w'_1} g_2^{w'_2}$$, then $$g_1^{w_1-w'_1} = g_2^{w'_2 - w_2},$$ and having $$g_2 = g_1^{x}$$ for some unknown $$x$$,
$$g_1^{w_1-w'_1} = g_1^{x(w'_2 - w_2)},$$ or equivalently $$w_1 - w'_1 = x(w'_2 - w_2)\mod q,$$
where $$q$$ is an order of the group.
Finally, $$x = (w_1 - w'_1)(w'_2 - w_2)^{-1}\mod q$$