Impact of super-polynomial extractors on the security of a zero-knowledge proof

Question

Interactive zero-knowledge arguments are proven to be secure in three parts:

1. completeness (the verifier accepts if the prover is honest)
2. soundness (a dishonest prover cannot convince a verifier)
3. zero-knowledgeness (the proof does not leak any information to the honest verifier)

Soundness is usually proven using some kind of extractor: by rewinding the protocol, often multiple times over, the verifier can send multiple challenges, and can in the end compute the witness that the prover is holding.

This talk by Benedikt Bünz mentions that there is a problem with the extractor of the original Bootle, J. et al. 2016 protocol (the predecessor to Bulletproofs): the extractor runs in super-polynomial time.

What is the impact of the super-polynomial complexity of an extractor? Is the mere existence of an extractor not enough to show that the prover has to hold a witness?

Answer 1

The philosophy behind the extractor and knowledge is that if the prover can generate the proof, then it could itself run the extractor. Therefore, if it can prove, then it knows the witness.

If the extractor runs in super polynomial time, then the prover itself cannot run the extractor. Note that if you took this to an extreme, then in exponential time it is always possible to just find the witness. So, any ZK proof can be said to be a proof of knowledge with an exponential-time extractor. But this is meaningless.

Technically, proofs of security of protocols that would use such a zero-knowledge proof of knowledge would break down.