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.
17
questions
0
votes
1
answer
60
views
Special Soundness $\Sigma$-Protocols
About the characterizations of Special Soundness, from Staking Sigmas we have that:
''A $\Sigma$-protocol $\Pi=(A,Z,\phi)$ is said to have ${\it special\ soundness}$ if there exists a PPT extractor $\...
- 187
0
votes
0
answers
40
views
Verifying a random subset of a parallel repitition of sigma protocols
Suppose a prover computes a non-interactive proof which is composed of $k$ parallel repetitions of a sigma protocol with binary challenges (and knowledge error $\frac{1}{2}$), composed in parallel and ...
- 413
0
votes
0
answers
43
views
A cryptographic proof system which uses rewinding to argue soundness but is not a proof of knowledge?
Are there any cryptographic proof systems that rewind the prover to argue soundness but are not proofs of knowledge? In particular, I would be very curious to see examples of proof systems where ...
0
votes
0
answers
46
views
What is this parameter? in Lyubashevsky's ID-scheme
I am studying Lybashevsky's ID-scheme from the article Fiat-Shamir With Aborts: Applications to Lattice and Factoring-Based Signatures(https://www.iacr.org/archive/asiacrypt2009/59120596/59120596.pdf) ...
- 335
1
vote
1
answer
79
views
Why I always obtain this soundness bound in parallel repetition of interactive proof systems
Fix an interactive proof system $(P,V)$ and denote by $(P_k,V_k)$ an interactive proof system in which the parties play in parallel $k$ copies of $(P,V)$ and for which $V_k$ accepts if and only if $V$ ...
- 722
1
vote
1
answer
168
views
Can we achieve statistical Completeness, Soundness and Zero Knowledge in an Interactive Proof?
The question is mainly stated in the title, sorry for it being a bit small of a question. I was reading about ZK proofs and I was wondering what do we know about their limits only their properties. Do ...
- 878
1
vote
0
answers
170
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 ...
- 385
4
votes
2
answers
877
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 ...
- 700
2
votes
0
answers
123
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. ...
- 548
0
votes
1
answer
55
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 (...
- 117
4
votes
0
answers
836
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 $\...
- 173
2
votes
1
answer
142
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 ...
- 23
1
vote
1
answer
90
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-...
- 2,320
1
vote
1
answer
142
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$ ...
- 155
4
votes
1
answer
1k
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 ...
- 155
7
votes
1
answer
505
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 ...
- 722
28
votes
1
answer
6k
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 ...
- 571