2
$\begingroup$

I'm somewhat new to cryptography and I've been looking at knowledge extractors in proofs of knowledge and I am a little confused by the use of somewhat different definitions.

In textbooks or early papers, (as an example see Definition 4.7.2 in Goldreich's textbook [G]), I've seen the knowledge property defined roughly as $\exists$ $\mathcal{E}$ such that $\forall$ PPT provers $P^*$ that convince the verifier, $\mathcal{E}^{P^*}$ can output the witness.

However, when looking at recent zkSNARK papers in particular, I see the order of the quantifiers reversed (see for example Definition 2.5 in Spartan [S]). Here, the knowledge property is of the form as $\forall$ PPT $P^*$, there exists $\mathcal{E}$ ...

Furthermore, I was also looking at straight-line extractors. Here, for example Definition 5 in [P], knowledge soundness is once again of the form as $\forall$ PPT $P^*$, there exists $\mathcal{E}$ ...

Can someone explain the reason for why the definitions are differently written?

Refs:

[G] Goldreich, Foundations of Cryptography, Vol 1

[P]: Rafael Pass. On deniability in the common reference string and random oracle model. CRYPTO 2003

[S] Srinath Setty. Spartan: Efficient and general-purpose zkSNARKs without trusted setup. CRYPTO 2020

$\endgroup$

1 Answer 1

1
$\begingroup$

That is kind of unusual and I'm not really sure about why the difference exists, so here are my best guesses.

To take a step back, usually the extractor is used to show that if an adversary breaks soundness, then you can solve some hard problem (e.g., discrete log). A proof of this would work something like this: suppose you have an adversary $\mathcal{A}$ against the scheme, and an extractor $\mathcal{E}$ against the adversary. Then you use the group problem to cook up parameters to the proof-of-knowledge scheme, you feed those to $\mathcal{E}$, then $\mathcal{E}$ implicitly uses $\mathcal{A}$, and eventually outputs a witness. The witness should solve the group problem.

In this case, I think it's fine to have $\mathcal{E}$ be specific to the adversary $\mathcal{A}$, i.e., the order of quantifiers you saw in the [S] and [P]. You will still be able to solve the group problem if an adversary and extractor exist, hence such adversaries do not exist if the problem is hard.

But typically to prove soundness of the scheme, you construct an extractor without using any specific knowledge of $\mathcal{A}$. So this would be a "univeral" extractor satisfying the definition in [G]. Think about a Schnorr proof: it works by just rewinding once, and it doesn't care about what the adversary does. Typically in such a proof you don't make any assumptions on the adversary (besides that it works), so your extractor will come out universal anyway. It would be a pretty weird scheme that would need you to separate different adversaries into different cases to find an extractor for each.

Since the definition in [G] implies the other definitions, it's a stronger condition so maybe people choose to use the adversary-specific extractors because it's technically a weaker criteria. But all the proofs I've seen are essentially proofs of the [G] definition, because they're not specific to the adversary.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.