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?


1 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.

  • $\begingroup$ Aha, that makes a lot of sense. I had always thought that the extractor could run on any non-determninistic Turing machine, but of course even then the prover still needs to fulfil an exponential amount of challenges. Thanks for clarifying! $\endgroup$ Feb 20, 2021 at 21:35

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.