Join Log in
Score:4
baro77 avatar Crypto

Relation between Knowledge extractor and soundness in ZKPoK

gd flag
baro77

Reading Why Zk-SNARKs are Argument of Knowledge if a Knowledge Extractor exists? I feel confused by OP first statement:

From what I know, proving the existance of a Knowledge Extractor implies perfect soundness.

Answer focuses on soundness not necessarily being perfect, but it seems implicitly confirming the soundness implication by the extractor.

First of all let me state that when I read "soundness" I think to the property of IPs stating that no Prover strategy can convince the Verifier of a symbol not belonging to the Language with more than negligible probability... which seems a quite different "object" than an extractor "spilling out" the witness, so it's difficult for me to get an at least naive idea of that supposed implication.

However I was beginning to believe it, because of sources I found, e.g.:

[...] the soundness property is replaced by a knowledge-extraction property [...]

When it comes to demonstrating the soundness of a proof of knowledge, we have a really nice formal approach. Just as with the Simulator we discussed above, we need to demonstrate the existence of a special algorithm. This algorithm is called a knowledge extractor, and it does exactly what it claims to. A knowledge extractor (or just ‘Extractor’ for short) is a special type of Verifier that interacts with a Prover, and — if the Prover succeeds in completing the proof — the Extractor should be able to extract the Prover’s original secret. And this answers our question above. To prove soundness for a proof of knowledge, we must show that an Extractor exists for every possible Prover.

HOWEVER in paragraph 4.5 "What about soundness?" of On Defining Proofs of Knowledge where Bellare and Goldreich deal with their formulation of PoK versus previous ones (https://www.wisdom.weizmann.ac.il/~oded/PS/pok.ps) I have found these words:

We note that our definition makes no requirement for the case $x$ not in $L_R$. In particular, soundness (i.e., a bound on the prover's ability to lead the verifier to accept $x$ not in $L_R$) is not required. Consequently, a knowledge verifier for $R$ does not necessarily define an interactive proof of membership in $L_R$. This is in contrast to previous definitions; they had the "validity" condition imply the soundness condition, so that the latter always held. We feel that our "decoupling" of soundness from validity is justified both conceptually and in the light of certain applications.

By the way, it's the same point of view of famous Golderich's "Foundation of Cryptography", section 4.7.

So again I'm dubious about: Knowledge Extractor $=>$ Soundness

Coud someone state the implication proof explicitly or at least give me any hints about it?

Or maybe existence of Knowledge Extractor in some way by itself avoids the Verifier to be convinced of a "witness" not really known by the Prover, so it could be considered a sort of "soundness property" even if of different nature with respect to usual ones? (this point of view seems confirmed by Geoffroy Couteau in the originally cited question/answer exchange when he writes:

Yes, there are several dimensions in the flavor of soundness: whether you have "membership soundness" or "knowledge soundness" is one (I usually say 'knowledge extractability" in my paper to distinguish from the usual soundness)

however if that's the case I would have expected him to correct that "implies" by OP)

Sorry for having been wordy, I hope to have described my doubts in an understandable way.

131
0 + 0
DiamondDuck avatar
hu flag
DiamondDuck
I do not fully understand your question. For soundness IP, if you take DLOG as the language, an empty string from prover should convince Verifier$(X=g^x)$ that $X$ is in the language. But it does not convey the idea that the prover knows $x$. So the knowledge extractor is for knowledge soundness (implying the prover actually knows $x$ to produce the valid proof).
0
Reply
baro77 avatar
gd flag
baro77
IPs are well defined by Completeness and Soundness, while for PoK Completeness and Knowledge Extractor Existence are cited. There can be two explanations I guess: KE => usual Soundness property or KE represents a quite different but anyway adequate flavour of soundness. Literature doesn't help me to understand which is the right case and how to demonstrate it (or at leat feel it reasonable)
0
Reply
Score:5
Geoffroy Couteau avatar Crypto
cn flag
Geoffroy Couteau

Knowledge Extractability is a strictly stronger property than soundness. Below, I will sketch why unconditional knowledge extractability implies statistical soundness. In informal terms, statistical soundness states:

"If the statement is incorrect, then any malicious prover will have negligible probability of producing an accepting proof"

On the other hand, KE states:

(*) "Take any (possibly malicious) prover algorithm, that produces an accepting proof with non-negligible probability. Then there is an (expected polynomial time) extractor that interacts with this prover and recovers a witness (i.e., a proof) that the statement is true".

Formulated as above, it should be relatively clear that KE implies soundness: if the KE is guaranteed to find a witness for the statement being true, it implies in particular that the statement is true. In other terms, (*) implies:

"If there is a (possibly malicious) prover algorithm that produces an accepting proof with non-negligible probability, then the statement is necessarily true"

Taking the contraposition gives: "If the statement is incorrect, then no prover algorithm can produce an accepting proof with non-negligible probability",

which is exactly statistical soundness. Note that this does not give you perfect soundness: for this, you would need a form of "super strong" knowledge extractability which would guarantee extraction of a witness from any (possibly malicious) prover that outputs an accepting proof with any probability $p>0$.

Note that there also exist situations where we can only prove a computational form of KE, such as "either we can extract a witness from this polynomially-bounded successful prover, or we can use the prover to break this hard problem". In this case, computational KE implies computational soundness.

0 + 0
Score:0
baro77 avatar Crypto
gd flag
baro77

Thank you! Now your sketch helped me to not get lost anymore in formal details of FoC 4.7, and to also understand When knowledge soundness implies soundness , found in the meanwhile and which is worth to be cited here, I guess (that's why I'm writing this as an answer, as well)

I think my confusion stemmed first of all by me not being a specialist of this field ;-) and later from Goldreich keen choice to not define KE Validity for false statements and his following deduction about not being able to deal with false statements case (even if your sketch make me think that, even if not defined in that case, it seems impossible that a KE can return a false statement's inexistent witness, so KE returning a witness really implies statement being true, so your logic chain seems valid also under Goldreich's assumptions)

0 + 0
ธงชาติไทย
Elon Musk
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.