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.
14
questions
0
votes
0
answers
36
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) ...
- 117
1
vote
1
answer
42
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$ ...
- 593
1
vote
1
answer
112
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 ...
- 826
1
vote
0
answers
100
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 ...
- 335
4
votes
2
answers
471
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 ...
- 670
2
votes
0
answers
106
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. ...
- 474
0
votes
1
answer
50
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
464
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
115
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
80
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,250
1
vote
1
answer
113
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
789
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
491
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 ...
- 593
27
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 ...
- 561