Paper 2018/896

Proofs of Ignorance and Applications to 2-Message Witness Hiding

Apoorvaa Deshpande and Yael Kalai


We consider the following paradoxical question: Can one prove lack of knowledge? We define the notion of 'Proofs of Ignorance', construct such proofs, and use these proofs to construct a 2-message witness hiding protocol for all of NP. More specifically, we define a proof of ignorance (PoI) with respect to any language L in NP and distribution D over instances in L. Loosely speaking, such a proof system allows a prover to generate an instance x according to D along with a proof that she does not know a witness corresponding to x. We construct construct a PoI protocol for any random self-reducible NP language L that is hard on average. Our PoI protocol is non-interactive assuming the existence of a common reference string. We use such a PoI protocol to construct a 2-message witness hiding protocol for NP with adaptive soundness. Constructing a 2-message WH protocol for all of NP has been a long standing open problem. We construct our witness hiding protocol using the following ingredients (where T is any super-polynomial function in the security parameter): 1. T-secure PoI protocol, 2. T-secure non-interactive witness indistinguishable (NIWI) proofs, 3. T-secure rerandomizable encryption with strong KDM security with bounded auxiliary input, where the first two ingredients can be constructed based on the $T$-security of DLIN. At the heart of our witness-hiding proof is a new non-black-box technique. As opposed to previous works, we do not apply an efficiently computable function to the code of the cheating verifier, rather we resort to a form of case analysis and show that the prover's message can be simulated in both cases, without knowing in which case we reside.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Witness HidingWitness IndistinguishabilityZero Knowledge
Contact author(s)
apoorvaa_deshpande @ brown edu
2019-03-02: last of 2 revisions
2018-09-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Apoorvaa Deshpande and Yael Kalai},
      title = {Proofs of Ignorance and Applications to 2-Message Witness Hiding},
      howpublished = {Cryptology ePrint Archive, Paper 2018/896},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.