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
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 $\...
Cristian Baeza's user avatar
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 ...
Lev's user avatar
  • 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 ...
Matan Shtepel's user avatar
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) ...
Rory's user avatar
  • 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$ ...
Bean Guy's user avatar
  • 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 ...
tur11ng's user avatar
  • 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 ...
A.Solei's user avatar
  • 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 ...
baro77's user avatar
  • 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. ...
pintor's user avatar
  • 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 (...
MR.-c's user avatar
  • 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 $\...
jvdh's user avatar
  • 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 ...
Mateo's user avatar
  • 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-...
Ruben De Smet's user avatar
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$ ...
Gabi G's user avatar
  • 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 ...
E. Postlethwaite's user avatar
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 ...
Bean Guy's user avatar
  • 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 ...
MH Samadani's user avatar