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 𝖭𝖯∩𝖼𝗈𝖭𝖯 .|
|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|
|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)|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.