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.
6
questions with no upvoted or accepted answers
4
votes
0
answers
1k
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
0
answers
130
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. ...
1
vote
0
answers
198
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 ...
0
votes
0
answers
42
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 ...
0
votes
0
answers
50
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) ...