26
votes
Accepted
what is the difference between proofs and arguments of knowledge?
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 ...
13
votes
Accepted
What does it mean to be "sound"?
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 ...
7
votes
Accepted
Relation between Knowledge extractor and soundness in ZKPoK
Knowledge Extractability is a strictly stronger property than soundness. Below, I will sketch why unconditional knowledge extractability implies statistical soundness. In informal terms, statistical ...
7
votes
Accepted
When knowledge soundness implies soundness
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 ...
3
votes
Accepted
Can we achieve statistical Completeness, Soundness and Zero Knowledge in an Interactive Proof?
The class of languages having statistical (resp. perfect) zero-knowledge proofs (where completeness is perfect and soundness statistical) is called $\mathsf{SZK}$ (resp. $\mathsf{PZK}$). Here is what ...
3
votes
Accepted
Impact of super-polynomial extractors on the security of a zero-knowledge proof
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 ...
2
votes
Accepted
Dishonest verifier running a concurrent zero-knowledge protocol
The definition of soundness for an interactive (zero-knowledge) proof says that no prover can convince a verifier of a false statement (i.e., one not in the language in question), except with tiny ...
1
vote
Special Soundness $\Sigma$-Protocols
I'll focus on the definition/notation of Damgard since it's the one I am more familiar with. An important element of the definition is that both transcripts need to be with respect to the same first ...
1
vote
Why I always obtain this soundness bound in parallel repetition of interactive proof systems
Assuming we are not too concerned by the constraints of computational proof systems, parallel repetition emulates $k$ independent interactions, and the parallel verifier accepts only if all ...
1
vote
Relation between Knowledge extractor and soundness in ZKPoK
Thank you! Now your sketch helped me to not get lost anymore in formal details of FoC 4.7, and to also understand When knowledge soundness implies soundness , found in the meanwhile and which is worth ...
1
vote
Accepted
BA protocol soundness explanation
Soundness is the probability that the protocol works as intended and can be any real number greater than 0 and less than or equal to 1. Different designs will have different probabilities of working ...
1
vote
Accepted
Show that there is an efficient zero knowledge proof for any language $L \in NP$
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
soundness × 17zero-knowledge-proofs × 11
fiat-shamir × 3
provable-security × 2
lattice-crypto × 2
security-definition × 2
interactive-proofs × 2
completeness × 2
sigma-protocol × 2
signature × 1
algorithm-design × 1
attack × 1
terminology × 1
complexity × 1
commitments × 1
random-oracle-model × 1
man-in-the-middle × 1
snarks × 1
literature × 1