2
$\begingroup$

How do I calculate the soundness error of a sigma protocol, such as Schnorr's interactive protocol for knowledge of a discrete logarithm?

$\endgroup$
1
  • 1
    $\begingroup$ I suppose the general answer will depend on the protocol, but for Sigma protocols the soundness error is 1 over the cardinality of the challenge space, i.e. $2^{-t}$ for a $t$-bit challenge. I still haven't full understood the proof, but it is given here: cs.au.dk/~ivan/Sigma.pdf $\endgroup$ Dec 19, 2022 at 12:27

2 Answers 2

2
$\begingroup$

As far as I know, a general answer depends on protocol under analysis (as Schnorr) being a Proof of Knowledge (PoK) and not necessarily being a Sigma Protocol.


PRELIMINARIES

A Knowledge Extractor (KE) exists, implied by the protocol being a PoK, and roughly defined as:

an entity capable -outside the constraints of proof execution- of extracting the Witness W of the Prover’s knowledge, only $\forall$Prover* s.t. $P [$Verifier is convinced$]$ > $\eta$

where Prover* is a Prover with ANY strategy (so also a cheating one, not necessarily the one prescribed by the protocol).

It seems reasonable to define $\eta$ as "KE error", a threshold below which KE cannot extract W.


THESIS

The soundness error is $=\eta$


PROOF

KE extract W $\Longrightarrow$ statement is TRUE (because W is an evidence of the protocol's statement)

taking the contrapositive:

statement is FALSE $\Longrightarrow$ KE never extracts W

but from KE definition:

KE never extracts W $\Longrightarrow$ $\forall$Prover* $P [$Verifier is convinced$]$ $\leq$ $\eta$

chaining the two implications:

statement is FALSE $\Longrightarrow$ $\forall$Prover* $P [$Verifier is convinced$]$ $\leq$ $\eta$

which is exactly the soundness definition


CONCLUSIVE REMARKS

if $\eta$ = 0 we get perfect soundness , and $\eta$ < 1/2 leads to protocol statistical soundness by protocol repetition and majority voting ; when $\eta \geq$ 1/2 we are in the quite common case in which a satisfying PoK is obtained only by $n$ sequential repetitions of the original one: the resulting protocol can be proved to have KE Error = $\eta^n$, permitting again statistical soundness for a large enough $n$.

If you need more context you could try this: https://github.com/baro77/ZKbasicsCS (mine) or a lot of much better resources out there.

Hope I have helped you a bit

$\endgroup$
10
  • 1
    $\begingroup$ it has computational soundness, because it relies on discrete logarithm hardness assumption, so it can reduced to DLP problem (which is computational), aka: if you break soundness property, you also break DLP... so you trust soundness as much as you trust DLP hardness (and that "as much" is "computational") $\endgroup$
    – baro77
    Dec 20, 2022 at 14:31
  • 1
    $\begingroup$ soundness error is proved under bound computation assumptions (always the case when you deal with real world implementation of algos), and that's a stronger characterization than actual error value, so the soundness is computational (again, always the case when you deal with real world implementation of algos) For how soundness relies on DLP, you can check this (first 14 pages): github.com/AdamISZ/from0k2bp/blob/master/from0k2bp.pdf $\endgroup$
    – baro77
    Dec 21, 2022 at 15:46
  • 1
    $\begingroup$ imho your case doesn't qualify as a counter-example because P* statement (knowing x s.t. Gx=y, G=0, y!=0) is plainly false to everyone. PoK is not about pretending everything you would want, in fact it's about proving you know something which can exist: so imho your statements not only puts you out of Schnorr and DLP at all, but more, it's not a PoK $\endgroup$
    – baro77
    Dec 23, 2022 at 11:32
  • 1
    $\begingroup$ I see what you're saying, thank you. For anyone following this question thread in the future, I created a follow-up question here (crypto.stackexchange.com/q/103439/84785) with some more details, hoping to expand on this line of questioning. $\endgroup$ Dec 25, 2022 at 19:09
  • 1
    $\begingroup$ Schnorr's interactive protocol is a proof of knowledge, that is the soundness guarantee holds against unbounded adversaries: see Geoffroy's explanation. $\endgroup$
    – ckamath
    Dec 25, 2022 at 20:32
2
$\begingroup$

For a $\Sigma$ protocol with a challenge space $\mathcal C$, the soundness error is $1/c$ where $c = |\mathcal C|$. Alternatively, the error is $2^{-t}$ for a $t$-bit challenge.

The proof that I still don't fully understand is given in the paper "On $\Sigma$-protocols" by Ivan Damgård. But I think the intuition goes as follows:

If a cheating prover succeeds with probability more than $1/c$; therefore, they can answer more than one challenge. In turn, one can use the 2-extractability of the sigma protocols to extract the witness. This is probably not a very good summary of the proof so better look at the paper.

$\endgroup$
3
  • $\begingroup$ I have taken a look at that article. The point is: "Theorem 1. Let P be a Σ-protocol for relation R with challenge length t. Then P is a proof of knowledge with knowledge error 2^−t." (I haven't time to study it, sorry) Given that, you go on with the proof in my answer $\endgroup$
    – baro77
    Dec 20, 2022 at 14:53
  • $\begingroup$ @baro77, sorry, I am not sure that I follow what you mean. Would you mind clarifying? $\endgroup$ Dec 20, 2022 at 14:55
  • $\begingroup$ theorem 1 proof on page 5 and following proves a Σ-protocol has KE error = 2^-t ... if you understand that, the next step to pass from KE error to soundness error is in my answer to the OP $\endgroup$
    – baro77
    Dec 20, 2022 at 15:01

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.