0
$\begingroup$

About the characterizations of Special Soundness, from Staking Sigmas we have that:

''A $\Sigma$-protocol $\Pi=(A,Z,\phi)$ is said to have ${\it special\ soundness}$ if there exists a PPT extractor $\mathcal{E}$, such that given any two transcripts $(x,a,c,z)$ and $(x,a,c',z')$, where $c\ne c'$ and $\phi(x,a,c,z)=\phi(x,a,c',z')=1$, it holds that \begin{align*} \Pr[\mathcal{R}(x,w)=1|w\leftarrow\mathcal{E}(1^\lambda,x,a,c,z,c',z')]=1, \end{align*}''

which is essentially the same stated in On $\Sigma$-protocols with different notation:

''From any $x$ and any pair of accepting conversations on input $x$, $(a, e, z)$, $(a,e',z')$ where $e\ne e'$, one can efficiently compute $w$ such that $(x,w)\in R$. This is sometimes called the ${\it special\ soundness}$ property.''

So my question is, why is this a desirable property? shouldn't we want to avoid this? i.e. shouldn't it be infeasible for an extractor to retrieve the witness even if it produces two accepting transcripts?

$\endgroup$

1 Answer 1

1
$\begingroup$

I'll focus on the definition/notation of Damgard since it's the one I am more familiar with. An important element of the definition is that both transcripts need to be with respect to the same first message (the commitment) $a$, but with different challenges. So as long as this first message is probabilistic, one is unlikely to receive two transcripts with the same $a$ when interacting with an honest prover.

This was why the definition is not problematic. The reasons why this is a desirable property are the following.

First, it implies regular soundness: if $x\notin L$, then for any commitment $a$, being able to respond to two different challenges $e\neq e'$ means being able to reconstruct a witness for $x$. Since $x\notin L$, there is no such witness, so this means there is a single challenge that will be accepted and the probability of accepting a false statement is $\frac 1M$ where $M$ is the size of the challenge space. I've also seen this unique challenge property being useful when proving other properties of a scheme.

Secondly, special soundness also implies knowledge soundness, i.e. a special sound proof is a proof of knowledge. To show this, one has to construct an extractor that interacts with a prover and produces a valid witness. If the proof is special sound, then the extractor can proceed as follows: run the prover until it outputs the first message $a$, send it a challenge $e$ and get a response $z$, now rewind the prover to its state before receiving the challenge, send it a different challenge $e'$ and get a different response $z'$. If both transcripts are accepting, then by the special soundness property it is possible to recover a witness for $x$ in polynomial time.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.