0
$\begingroup$

Referring to an old but very nice paper on Witness Indistinguishability and Witness Hiding (link).

On page 4, in theorem 3.2, the author explained it in three points, but I have few queries.

In point 2: "he sends w to $\bar V$, showing that he too knows w"

Why is it required? What value it is adding?

In point 3: "$\bar P$ proves his knowledge of w"

But, $\bar P$ never had w, then how can it prove?

In next paragraph, he also explains how two parallel executions $(\bar P_1, \bar V)$ and $(\bar P_2, \bar V)$.

But, since I could not grasp the earlier part, I am having hard time understanding this also.

Can somebody please provide more insight to this?

$\endgroup$

1 Answer 1

0
$\begingroup$

It is a contrived example to show that zero-knowledge is not preserved in parallel repetitions. By itself, the protocol is zero-knowledge since the only way that $\bar V$ can receive the witness $w$ from $\bar P$ is by proving to it that it does know $w$ using the proof system $(P,V)$ and with $\bar V$ acting as $P$. If $\bar V$ can't prove knowledge of $w$, then $\bar P$ proceeds as $P$ to prove knowledge of $w$ (in zero-knowledge).

The issue that the authors want to highlight occurs when two instances of the scheme are executed in parallel. In this case, the verifier can send $0$ to $\bar P_1$ so that $\bar P_1$ proves knowledge of $w$ to $\bar V$. But then $\bar V$ can send $0$ to $\bar P_2$ and prove knowledge of $w$ using the proof provided by $\bar P_1$. $\bar P_2$ will accept the proof and give $w$ to $\bar V$. In other words, the verifier makes both provers talk to each other.

$\endgroup$
0

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.