Join Log in
Score:4
avatar Crypto

2 different definitions of Special Soundness

cn flag
jvdh

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?

196
0 + 2
ming alex avatar
in flag
ming alex
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.
0
Reply
Mark avatar
ng flag
Mark
Mihir Bellare has [some notes](https://cseweb.ucsd.edu/~mihir/cse208-Wi20/main.pdf) on some of the (subtly different) different definitions within the world of NIZKs that may be of interest.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.