Does there exist any (im)possibility results for two-round private-coin non-auxiliary input zero-knowledge proofs for languages outside BPP?


1 Answer 1


Under the following assumptions there does not even exist three-round private-coin zero-knowledge proofs for languages outside BPP. See here.

The theorem holds assuming:

  • Sub-exponentially secure one-way functions.
  • Sub-exponentially secure indistinguishability obfuscation for circuits.
  • Exponentially secure input-hiding obfuscation for multi-bit point functions
  • 2
    $\begingroup$ Hamidreza explicitly talks about non auxiliary input ZK. The paper you quote only deals with auxiliary input ZK. Further, for that case it would be overkill. 2-round AI-ZK is already ruled out unconditionally by Goldreich and Oren. $\endgroup$
    – Maeher
    Jul 30, 2019 at 13:30

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.