Towards non-interactive witness hiding

Benjamin Kuykendall, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 18th International Conference, TCC 2020, Proceedings
EditorsRafael Pass, Krzysztof Pietrzak
PublisherSpringer Science and Business Media Deutschland GmbH
Pages627-656
Number of pages30
ISBN (Print)9783030643744
DOIs
StatePublished - 2020
Event18th International Conference on Theory of Cryptography, TCCC 2020 - Durham, United States
Duration: Nov 16 2020Nov 19 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12550 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Conference on Theory of Cryptography, TCCC 2020
Country/TerritoryUnited States
CityDurham
Period11/16/2011/19/20

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Non-interactive proofs
  • Witness hiding

Fingerprint

Dive into the research topics of 'Towards non-interactive witness hiding'. Together they form a unique fingerprint.

Cite this