Skip to main content

Towards Non-interactive Witness Hiding

Author(s): Kuykendall, Benjamin; Zhandry, Mark

To refer to this page use:
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 π–­π–―βˆ©π–Όπ—ˆπ–­π–― .
Publication Date: 2020
Citation: Kuykendall, Benjamin, and Mark Zhandry. "Towards Non-interactive Witness Hiding." In Theory of Cryptography Conference (2020): pp. 627-656. doi:10.1007/978-3-030-64375-1_22
DOI: 10.1007/978-3-030-64375-1_22
ISSN: 0302-9743
EISSN: 1611-3349
Pages: 627 - 656
Type of Material: Conference Article
Journal/Proceeding Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.