For clarification, the protocol works as follows: $P$ wants to convince $V$ that he knows $x$ such that $g^x=y$, where $g,y\in\mathbb{G}$ of order $p$; they perform the following steps:
- $P$ samples $k\stackrel{R}\leftarrow\mathbb{Z}/p\mathbb{Z}$ uniformly at random, computes commitment $r\leftarrow g^k$, and sends $r$ to $V$.
- $V$ samples a challenge $e\stackrel{R}\leftarrow\mathcal{C}$ from a challenge set $\mathcal{C}$ (e.g. $\mathcal{C}=\mathbb{Z}/p\mathbb{Z}$) and sends $e$ to $P$.
- $P$ computes a response $s\leftarrow k+e\cdot x$ and sends $s$ to $V$.
$V$ then determines whether they accept the transcript $(r,e,s)$ by checking $r\stackrel?=g^s\cdot y^{-e}$.
I know the protocol is special sound, since from two transcripts $(r,e,s)$ and $(r,e',s'$) such that $e\ne e'$ we can extract $x$ via:
$$
x\leftarrow\frac{s-s'}{e-e'}
$$
I read Ivan Damgard's paper (https://www.cs.au.dk/~ivan/Sigma.pdf ), which I believe proves that Sigma protocols (with special soundness) have knowledge soundness with knowledge error $\kappa=|\mathcal{C}|^{-1}$. In other words, a cheating prover $P^*$ can only convince the verifier they know $x$ with probability $\kappa$ if they do not.
This is where my first question comes in: is the knowledge soundness statistical or computational? In theory, a computationally unbound cheating prover could produce an accepting transcript $(r,e,s$) with advantage $\epsilon$, they could solve the discrete logarithm problem with advantage $\epsilon-\frac{\epsilon^2}{p}$ (Theorem 19.1 in https://toc.cryptobook.us/book.pdf). So in that sense, does the knowledge soundness of the protocol rely on the hardness of the discrete logarithm problem. If so, is it therefore computational?
My second question is similar, but regards the regular soundness of the protocol. Since the protocol is special sound, we know that for a given commitment $r$, if there are two accepting transactions $(r,e,s)$ and $(r,e',s')$ where $e\ne e'$ then we can extract $x$. Therefore if we have an invalid statement (i.e. a statement with no witnes), the probability of proving the invalid statement is at most $|\mathcal{C}|^{-1}$, since there exists only one $e$ that could produce an accepting statement for every possible commitment $r$. Therefore, even a computationally unbound prover could not hope to break soundness with an advantage greater than $|\mathcal{C}|^{-1}$. So in that sense, is the soundness statistical?
