Paper 2018/896
Proofs of Ignorance and Applications to 2Message 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 2message 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 selfreducible NP language L that is hard on average. Our PoI protocol is noninteractive assuming the existence of a common reference string. We use such a PoI protocol to construct a 2message witness hiding protocol for NP with adaptive soundness. Constructing a 2message 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 superpolynomial function in the security parameter): 1. Tsecure PoI protocol, 2. Tsecure noninteractive witness indistinguishable (NIWI) proofs, 3. Tsecure 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 witnesshiding proof is a new nonblackbox 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.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 Witness HidingWitness IndistinguishabilityZero Knowledge
 Contact author(s)
 apoorvaa_deshpande @ brown edu
 History
 20190302: last of 2 revisions
 20180924: received
 See all versions
 Short URL
 https://ia.cr/2018/896
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/896, author = {Apoorvaa Deshpande and Yael Kalai}, title = {Proofs of Ignorance and Applications to 2Message Witness Hiding}, howpublished = {Cryptology ePrint Archive, Paper 2018/896}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/896}}, url = {https://eprint.iacr.org/2018/896} }