Score:2

How to calculate soundness error of a sigma protocol?

nl flag

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

Marc Ilunga avatar
tr flag
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: https://www.cs.au.dk/~ivan/Sigma.pdf
Score:2
gd flag

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

George Herbert avatar
nl flag
Many thanks. I read through that document. So looking at Schnorr's identification protocol it appears to have perfect completeness and perfect honest-verifier zero-knowledge, but I can't quite work out what "type" of soundness it has. It appears to have a soundness error inverse of the size of the challenge set, so is this computational soundness?
baro77 avatar
gd flag
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")
George Herbert avatar
nl flag
So is the soundness “type” (i.e computational/statistical/perfect) unrelated to the soundness error, which in this case I believe is 1/c where c is the size of the challenge set?
George Herbert avatar
nl flag
Also I am unsure what you mean by the soundness relying on the discrete logarithm hardness assumption. Suppose some computationally unbounded prover could break the discrete logarithm problem, how would this enable them to prove false statements?
baro77 avatar
gd flag
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): https://github.com/AdamISZ/from0k2bp/blob/master/from0k2bp.pdf
George Herbert avatar
nl flag
I read the first 14 pages thanks, but I'm still confused—I'll explain with an example. Let us have additive group (Z/pZ,+). A malicious prover P* wants to prove he knows x s.t. g\*x=y (additive notation) where g=0, y≠0. No x exists that satisfies the equation => the statement is invalid. BUT if P\* "guessed" the challenge e in advance, and produced commitment r=y\*e, then the transcript (r,e,s) would be valid (for any s), since V would test via g\*s+y\*e=y\*e=r. The prob of P\* guessing e is 1/p => P\* breaks soundness w/ prob 1/p. I guess my question is how the DLP is related to this?
baro77 avatar
gd flag
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
George Herbert avatar
nl flag
I see what you're saying, thank you. For anyone following this question thread in the future, I created a follow-up question here (https://crypto.stackexchange.com/q/103439/84785) with some more details, hoping to expand on this line of questioning.
ckamath avatar
ag flag
Schnorr's interactive protocol is a *proof of knowledge*, that is the soundness guarantee holds against unbounded adversaries: see [Geoffroy's explanation](https://crypto.stackexchange.com/a/56325/11441).
baro77 avatar
gd flag
wow thanks to ckamath and @GeoffroyCouteau (and George's perseverance) now I understand why my comments were wrong (I'm not deleting them for "history diligence" and to not break replies flow): I think now my knowledge of the topic has strengthened a bit. Re-checking bulletproofs PDF I now "see" the DLP assumption appears in soundness proof for set of vectors, but it's absent in legacy Schnorr. Thanks everyone!
Score:2
tr flag

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.

baro77 avatar
gd flag
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
Marc Ilunga avatar
tr flag
@baro77, sorry, I am not sure that I follow what you mean. Would you mind clarifying?
baro77 avatar
gd flag
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
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.