Questions tagged [soundness]

Soundness is a property of proof systems that requires no prover can make the verifier accept a wrong statement except with some small probability. The upper bound of this probability is referred to as the soundness error of a proof system.

Filter by
Sorted by
Tagged with
4
votes
0answers
67 views

2 different definitions of Special Soundness

There are 2 different definitions of special soundness in the literature: (1) can be found in Damgard: We say that a Sigma-protocol $\Pi$ satisfies special soundness, if there exists a PPT extractor $\...
2
votes
1answer
53 views

Dishonest verifier running a concurrent zero-knowledge protocol

Suppose Alice and Bob are engaged in the graph 3-colorability Zero-knowledge protocol in which Alice permutes a coloring $\varphi:V\rightarrow \{1,2,3\}$ for a graph $G(V,E)$, and then sends a ...
1
vote
1answer
51 views

Impact of super-polynomial extractors on the security of a zero-knowledge proof

Interactive zero-knowledge arguments are proven to be secure in three parts: completeness (the verifier accepts if the prover is honest) soundness (a dishonest prover cannot convince a verifier) zero-...
1
vote
1answer
69 views

Show that there is an efficient zero knowledge proof for any language $L \in NP$

Let $(P,V)$ be an efficient zero-knowledge interactive proof for some language $A \in NP$ that is $(T,\epsilon)-\text{sound}$ and $(T,\epsilon)-\text{ZK}$. I want to show that for every language $L$ ...
0
votes
0answers
38 views

Auxiliary Input and the Soundness of Arguments

Interactive proof systems are often defined such that the interacting parties have access to some arbitrary auxiliary input, as in e.g. Def 4.2.10 of G where a pair of interactive machines $(P, V)$ ...
2
votes
1answer
209 views

When knowledge soundness implies soundness

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 ...
7
votes
1answer
455 views

What does it mean to be "sound"?

I've been reading this in many places and I still don't properly understand what it means to be "sound". As an example of what I am asking for: The Fiat-Shamir transfrom is sound in the ...
19
votes
1answer
4k views

what is the difference between proofs and arguments of knowledge?

What is the difference between proofs and arguments of knowledge in the context of zero-knowledge? I have read this sentence in this ePrint: It is useful to distinguish between zero-knowledge ...