$\Sigma$-protocols formal definition

 

Following 1 and some modern notations, I aim to describe a formal definition of a $3$-step interactive $\Sigma$-protocol with formal proofs, to help young engineers prove their $\Sigma$-protocols security. So:

For an NP relation $\mathcal{R}$ a $\Sigma$-protocol is a $3$-step protocol between the Prover and the Verifier consisting of three algorithms $\sigma_{com}, \sigma_{resp}, \sigma_{ver}$ with respect to the security parameter $\lambda$ and with the following definition:

  • $\sigma_{com}^\lambda(x, w) \rightarrow (t, i)$: for the public input $x$, and witness $w$ it generates a commitment $t$ and some side information $i$;

  • $\sigma_{resp}^\lambda(x,w,i,c) \rightarrow s$: for the public input $x$, witness $w$, and side information $i$ it generates a response $s$ for the challenge $c \in {0,1}^\lambda$;

  • $\sigma_{ver}^\lambda(t,c,x,s) \rightarrow {0, 1}$: for the public input $x$, the response $s$, the challenge $c$, and the commitment $t$ it outputs bit $b \in {0,1}$ assuming $(x, w) \in \mathcal{R}$ if $b = 1$ and $(x, w) \notin \mathcal{R}$ otherwise.

A $\Sigma$-protocol has the following properties:

Completeness

A $\Sigma$-protocol is said to be complete if for any pair $(x,w)$, such that $(x,w) \in \mathcal{R}$, and any challenge $c\in {0,1}^\lambda$:

\[Pr\Big[\sigma_{ver}^\lambda(t,c,x,s) = 1\Big] \geq 1 - \mathsf{negl}(\lambda).\]

Special Soundness

A $\Sigma$-protocol is said to be special sound if there exists a special polynomial-time extractor function $\mathcal{E}$ such that for any two given transcripts $(t,c,x,s)$ and $(t,\hat{c},x,\hat{s})$ where $c \neq \hat{c}$ and $\sigma_{ver}^\lambda(t,c,x,s) = \sigma_{ver}^\lambda(t,\hat{c},x,\hat{s}) = 1$:

\[Pr\Big[(x,w) \in \mathcal{R} \;\Big|\; w = \mathcal{E}(t,x,c,s,\hat{c},\hat{s})\Big] \geq 1 - \mathsf{negl}(\lambda).\]

More precisely, it means that for any two random, distinct challenges, the knowledge of the responses for the same commitment allows the verifier to recover the witness by a polynomial-time algorithm.

It is also said that a $\Sigma$-protocol is $k$-special sound if the above property achieved using $k$ different challenges.

Special Honest-Verifier Zero-Knowledge

A $\Sigma$-protocol is said to be special honest-verifier zero-knowledge if there exists a special polynomial-time simulator function $\mathcal{S}$ that enables the generation of an accepting transcript by the verifier using selected uniformly and independently a challenge $c \leftarrow \mathbb{F}$ and a response $s \leftarrow \mathbb{F}$:

\[Pr\Big[\sigma_{ver}^\lambda(t,c,x,s) = 1\;\Big|\; t = \mathcal{S}(x,c,s) \Big] \geq 1 - \mathsf{negl}(\lambda).\]

Transcripts ${(t, c, s)}$ generated by this process are assumed to be indistinguishable from real transcripts that appear during the protocol walkthrough between the honest prover and the honest verifier.

Why special soundness proves the soundness?

Imagine we have a cheating prover. By the definition, we assume that the cheating prover does not know a witness. If we can prove the special soundness, then it becomes able to recover a witness. But, from our initial assumption having a cheating prover such witness does not exist.

So, the cheating prover can give only one answer per commitment. To give such answer, a cheating prover should guess the incoming challenge before it will be supplied. If challenge is a bit string of size $\lambda$ then the probability to guess it is $2^{-\lambda}$, which means that our $\Sigma$-protocol has a soundness error $2^{-\lambda}$.

  1. Ivan Damgard. “On Σ-protocols”. CPT 2010, v.2. 2010 URL