Cryptology ePrint Archive: Report 2020/1205

Towards Non-Interactive Witness Hiding

Benjamin Kuykendall and Mark Zhandry

Abstract: Witness hiding proofs require that the verifier cannot find a witness after seeing a proof. The exact round complexity needed for witness hiding proofs has so far remained an open question. In this work, we provide compelling evidence that witness hiding proofs are achievable non-interactively for wide classes of languages. We use non-interactive witness indistinguishable proofs as the basis for all of our protocols. We give four schemes in different settings under different assumptions: A universal non-interactive proof that is witness hiding as long as any proof system, possibly an inefficient and/or non-uniform scheme, is witness hiding, has a known bound on verifier runtime, and has short proofs of soundness. A non-uniform non-interactive protocol justified under a worst-case complexity assumption that is witness hiding and efficient, but may not have short proofs of soundness. A new security analysis of the two-message argument of Pass [Crypto 2003], showing witness hiding for any non-uniformly hard distribution. We propose a heuristic approach to removing the first message, yielding a non-interactive argument. A witness hiding non-interactive proof system for languages with unique witnesses, assuming the non-existence of a weak form of witness encryption for any language in NP ∩ coNP.

Category / Keywords: foundations / witness hiding, non-interactive proofs

Original Publication (in the same form): IACR-TCC-2020

Date: received 1 Oct 2020

Contact author: brk at princeton edu

Available format(s): PDF | BibTeX Citation

Version: 20201006:093734 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]