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 $\mathcal{E}$, such that given any pair of accepting transcripts $(com,ch_1,resp_1),(com,ch_2,resp_2)$ with $ch_1\neq ch_2$, $\mathcal{E}$ can recover $sk$.

(2) can be found in Katz: Digital Signatures:

$\Pi$ satisfies special soundness, if the following is negligible in $\lambda$ for all PPT adversaries $\mathcal{A}$:

\begin{align} \operatorname{Pr} \left[ \begin{array}{c} (pk,sk) \gets \mathrm{keygen}(\lambda) \\ (com,ch_1,resp_1,ch_2,resp_2) \gets\mathcal{A}(pk) \end{array} : \begin{array}{c} ch_1\neq ch_2\\ \land\\ (com,ch_1,resp_1),(com,ch_2,resp_2) \\ \text{are both accepting transcripts.} \end{array} \right] \end{align}

I believe (1) is strictly stronger than (2). Is that correct?

  • $\begingroup$ Yes, but less formalized than (2). Actually, (1) implies the notion of proof of knowlege, which can be think of as special soundness, duo to the knowledge can be extracted by the PPT extractor. $\endgroup$
    – X.H. Yue
    Commented Aug 27, 2021 at 12:34
  • $\begingroup$ Mihir Bellare has some notes on some of the (subtly different) different definitions within the world of NIZKs that may be of interest. $\endgroup$
    – Mark Schultz-Wu
    Commented Aug 30, 2021 at 17:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.