You are looking at a specific version 20201006:093734 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in TCC 2020
Keywords
witness hidingnon-interactive proofs
Contact author(s)
brk @ princeton edu
History
2020-10-06: received
Short URL
https://ia.cr/2020/1205
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.