4
$\begingroup$

In the work of Bellare–Goldreich that defines knowledge soundness BG92, the discussion of Section 4.5 specifically decouples knowledge soundness from soundness. That is, proving knowledge soundness for some verifier $V$ says nothing about the soundness of some pair $(P^*, V)$, for arbitrary (cheating) prover $P^*$.

However, in various works, notes, and related notions, knowledge soundness is taken to imply soundness.

In Lin03, arguments of knowledge are defined in Definition 9, and in the discussion below are said to directly imply soundness error at most the knowledge error. In GI08, their particular notion of Witness-Extended Emulation, a more robust notion of knowledge, implies soundness. Finally, in the notes of Bar07, the definition of knowledge soundness given is said to imply a soundness error at the most the knowledge error, just as in Lin03.

The one thing all the above examples have in common, which also differs from BG92, is that they restrict the class of provers $P^*$ against which knowledge soundness is proven for $V$ to at most expected polynomial time.

Intuitively, this seems like it should be the reason for knowledge soundness implying soundness, especially in light of the discussion in Lin03. Can anyone give a more a explicit answer about why Section 4.5 of BG92 is not relevant in these cases?

$\endgroup$

1 Answer 1

7
$\begingroup$

The difference is that in Section 4.5, knowledge soundness (i.e., extraction) is required to hold only for every $x\in L_R$, and so there is no requirement at all for the case that $x$ is not in the language. In contrast, in Definition 9 of Lin03, the knowledge soundness (i.e., extraction) is required to hold for all $x$. This implies soundness since you cannot extract a witness for $x\notin L_R$, and so the verifier cannot accept in this case (except with probability of the knowledge error).

Note that this is orthogonal to the question of whether or not $P^*$ is efficient (i.e., whether it's a proof versus an argument).

$\endgroup$
1
  • $\begingroup$ I see what I overlooked, thank you for the quick repsonse! $\endgroup$ Nov 3, 2020 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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