Sigma protocol: witness hiding

Question

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...

Answer 1

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$$

The first your point is rather due to witness-indistinguishability property