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
1 vote
0 answers
45 views

Extractor in knowledge-soundness vs extractor in witness-extended emulation

In the knowledge soundness definition page 8 of Groth16, it says: The extractor gets full access to the adversary’s state, including any random coins. My question is why full access? Why we just don't ...
user avatar
  • 315
4 votes
2 answers
155 views

Relation between Knowledge extractor and soundness in ZKPoK

Reading Why Zk-SNARKs are Argument of Knowledge if a Knowledge Extractor exists? I feel confused by OP first statement: From what I know, proving the existance of a Knowledge Extractor implies ...
user avatar
  • 447
2 votes
0 answers
90 views

How to extract witness from a non-interactive lattice-based proof?

I'm trying to figure out how to construct an extractor for a non-interactive lattice-based proof. Specifically, I'm curious about the Fiat-Shamir transform applied to a five-move interactive protocol. ...
user avatar
  • 400
0 votes
1 answer
47 views

BA protocol soundness explanation

I was reading the following paper BA-made it trivial and when talking about BA agreement protocol in page 3, I didn't understand what it meant by soundness here. A protocol P is an arbitrary-value (...
user avatar
  • 117
4 votes
0 answers
210 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 $\...
user avatar
  • 173
2 votes
1 answer
79 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 ...
user avatar
  • 23
1 vote
1 answer
68 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-...
user avatar
1 vote
1 answer
94 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$ ...
user avatar
  • 155
3 votes
1 answer
431 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 ...
user avatar
7 votes
1 answer
475 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 ...
user avatar
  • 511
26 votes
1 answer
5k 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 ...
user avatar