From what I know, proving the existance of a Knowledge Extractor implies perfect soundness.
So why in zk-SNARKs (and similar) we talk about Arguments of Knowledge, where the soundness property is only computational (a.k.a, secure only from computationally bounded Provers), if a Knowledge Extractor also exists? Am I missing something? Maybe a Knowledge Extractor can be proven in different "levels" of security (computational, statistical and perfect)? I never saw that until now tho, and I've always seen Knowledge Extractors as something different to prove, and not directly linked to the soundness property, so I can't figure out an answer.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ "On defining proofs of knowledge" by Bellare and Goldreich: to name it "a proof of knowledge" one should present an explicit "extractor" algorithm. $\endgroup$– Vadym FedyukovychCommented Nov 10, 2021 at 19:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Knowledge soundness can indeed be computational or statistical. There are some classical example, if you want some illustration: the Sigma protocol for correct opening of the Damgard-Fujisaki commitment scheme (a variant of Pedersen over groups of hidden order) is knowledge sound under the RSA assumption (see here). Intuitively, when you go through the proof, this means that your extractor works only if a certain condition is met, and you can show that this condition will always be met, but only if the malicious prover cannot break some hard problem.
SNARKs are an even stranger beast: here, the existence of the efficient extractor itself is essentially the assumption.
So, if you prove unconditionally that there is an extractor, it indeed implies perfect soundness. But if you prove "either there is an extractor or we can break hard problem X", or if the existence of the extractor is actually part of the assumption itself, you clearly don't get perfect soundness as a consequence, only computational soundness.
answered Nov 8, 2021 at 19:12
-
$\begingroup$ Thank you very much Geoffroy! So, if I understood well, soundness, in addition to its definition, can also be categorized in different ways if an extractor exists and depending on the assumptions made for its existance. Those can be computational or statistical (or, eventually, perfect if its proven unconditionally). When talking about SNARKS, we assume that an extractor exists for the arguments, and that makes so that the soundness property is also computationally sound, meaning an extractor exists but only if the Prover is computationally bounded. $\endgroup$ Commented Nov 8, 2021 at 20:32
-
$\begingroup$ 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), and whether you have computational or statistical is another dimension. And yes, the assumption in SNARKs basically says "if the prover is bounded and makes a successful proof, then an extractor exists". $\endgroup$ Commented Nov 9, 2021 at 14:46