18

Yes, you are right. In a proof, the soundness holds against a computationally unbounded prover and in an argument, the soundness only holds against a polynomially bounded prover. Arguments are thus often called "computationally sound proofs".


13

An interactive or non-interactive protocol is said to be sound for a language $\mathcal{L}$ if it is "hard" for a (malicious) prover $\textsf{P}$ to convince a verifier $\textsf{V}$ of a statement $I\not\in\mathcal{L}$. Depending on how "hard" it actually is for $\textsf{P}$ to cheat, we either get a (interactive or non-interactive) proof ...


4

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


3

The philosophy behind the extractor and knowledge is that if the prover can generate the proof, then it could itself run the extractor. Therefore, if it can prove, then it knows the witness. If the extractor runs in super polynomial time, then the prover itself cannot run the extractor. Note that if you took this to an extreme, then in exponential time it is ...


1

Your idea is correct. Although the running times of the honest prover and verifier do increase by the running time of $R$, this (somewhat counterintuitively) does not affect the concrete bounds for soundness and ZK (at least how they are usually defined). Note that $T$-soundness does not really make sense for a proof system, since it is sound against even ...


Only top voted, non community-wiki answers of a minimum length are eligible