2
$\begingroup$

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:

  1. $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$.
  2. $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$.
  3. $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?

$\endgroup$
2
  • 1
    $\begingroup$ To offer to other readers a bit more context on this question, I guess it derives from me not being convincing or correct here: crypto.stackexchange.com/questions/103339/… I hope to also improve my knowledge from this new question $\endgroup$
    – baro77
    Dec 25, 2022 at 18:39
  • 1
    $\begingroup$ Schnorr's interactive protocol is a proof of knowledge, that is the (knowledge) soundness guarantee holds against unbounded adversaries: see Geoffroy's explanation. Plain soundness is vacuous for the discrete logarithm relation since it is total, i.e., $\forall y\exists x:g^x=y$: explanation here. $\endgroup$
    – ckamath
    Dec 25, 2022 at 20:44

1 Answer 1

3
$\begingroup$

I answered the first part of the question here: Schnorr is a statistical proof of knowledge, with knowledge error $1/p$ (or $1/|C|$ if you pick the challenge from $C$). That is, one can always extract the challenge, even against an unbounded prover, and no cryptographic assumption is required to prove the success of extraction.

As for the second question: for Schnorr, there is no notion of invalid statements. If $\mathbb{G}$ is a prime-order cyclic group with generator $g$, every element $h$ of $\mathbb{G}$ has a discrete logarithm in base $g$. In other words, the language is trivial: $\mathsf{L} = \{h \;:\; \exists x \in \mathbb{Z}_p, h = g^x\} = \mathbb{G}$. This is not an issue, precisely because the proof is a proof of knowledge: there is always a witness, but knowing the witness is non-trivial.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. With regards to there being no notion of invalid statements, suppose a malicious prover $P^*$ chose $g=1$ and $y\ne 1$ from some prime-order cyclic group $\mathbb{Z}/p\mathbb{Z}$. Would this not be considered an invalid statement, or do we simply not "allow it" at all in the relation $\mathcal{R}$? $\endgroup$ Dec 27, 2022 at 13:20
  • 2
    $\begingroup$ We simply don't allow it, since we insist that $g$ is a generator. Note that $\mathbb{Z}/p\mathbb{Z}$ is only a prime order cyclic group if you view it as an additive group, in which case $1$ is indeed a generator, and the relation becomes $\{y:\exists x \in \mathbb{Z}, y = x\cdot 1\}$, which is again trivial (but my previous point still stands if you consider instead a prime-order multiplicative subgroup of $\mathbb{Z}/p\mathbb{Z}$). $\endgroup$ Dec 27, 2022 at 18:35
  • $\begingroup$ Makes perfect sense, thank you very much. $\endgroup$ Dec 27, 2022 at 19:14

Your Answer

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

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