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

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

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

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

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

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

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( ...
Rory's user avatar
  • 335