Skip to main content

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
Filter by
Sorted by
Tagged with
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 $\...
jvdh's user avatar
  • 173
2 votes
0 answers
135 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
  • 558
1 vote
0 answers
207 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
  • 405
0 votes
0 answers
47 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
  • 468
0 votes
0 answers
53 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
49 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