2
$\begingroup$

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:

The protocol

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

$\endgroup$
1
$\begingroup$

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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.