Join Log in
Score:1
avatar Crypto

Why Zk-SNARKs are Argument of Knowledge if a Knowledge Extractor exists?

in flag
Andrea Farneti

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.

97
0 + 0
Vadym Fedyukovych avatar
in flag
Vadym Fedyukovych
"On defining proofs of knowledge" by Bellare and Goldreich: to name it "a proof of knowledge" one should present an explicit "extractor" algorithm.
0
Reply
Score:1
Geoffroy Couteau avatar Crypto
cn flag
Geoffroy Couteau

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.

0 + 0
in flag
Andrea Farneti
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.
0
Reply
Geoffroy Couteau avatar
cn flag
Geoffroy Couteau
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".
0
Reply
ธงชาติไทย
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.