Interactive zero-knowledge arguments are proven to be secure in three parts:
- completeness (the verifier accepts if the prover is honest)
- soundness (a dishonest prover cannot convince a verifier)
- 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?