Cryptology ePrint Archive: Report 2018/896

Proofs of Ignorance and Applications to 2-Message Witness Hiding

Apoorvaa Deshpande and Yael Kalai

Abstract: 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.

Category / Keywords: cryptographic protocols / Witness Hiding, Witness Indistinguishability, Zero Knowledge

Date: received 23 Sep 2018, last revised 2 Mar 2019

Contact author: apoorvaa_deshpande at brown edu

Available format(s): PDF | BibTeX Citation

Version: 20190302:205134 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]