We have lower bounds for classical zero-knowledge protocols (eg we cannot have 3-round zero-knowledge protocols for NP, with negligible soundness and black-box simulation). However, some of these lower bounds can be bypassed if we increase the power of the simulator.

For instance, if we allow the simulator to be exponential time, then the definition is equivalent to witness-indistinguishability, and we have a 3-round protocol for NP.

Are there any examples where a classical lower bound can be bypassed by allowing the simulator to be a quantum polynomial time algorithm?

  • $\begingroup$ Intuitively, such a thing would occur if the classical verifier could gain information from interacting with the prover, whereas the quantum verifier can compute this information itself. For example, the verifier could learn the factors of a large number, which a quantum simulator could compute efficiently. While I don't have a direct answer to your question, I suspect that a "bypass" as in your question would imply a quantum speedup for some problem related to the language being proven, which are usually hard in the case of no-go results. $\endgroup$
    – lamontap
    Apr 18, 2023 at 20:43


Your Answer

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