New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

# 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.

18 questions
Filter by
Sorted by
Tagged with
1 vote
43 views

### Showing special soundness for Dilithiums underlying $\Sigma$-protocol

I'm trying to prove the security of Dilithiums underlying $\Sigma$-protocol using the following theorem. Let $\Sigma=\left(\mathcal{P},\mathcal{V}\right)$ be a $\Sigma$-protocol on an effective ...
• 253
108 views

• 173
166 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
94 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,380
1 vote
175 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
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 ...
521 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 ...
• 742