TY - GEN
T1 - Towards non-interactive witness hiding
AU - Kuykendall, Benjamin
AU - Zhandry, Mark
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2020.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
KW - Non-interactive proofs
KW - Witness hiding
UR - http://www.scopus.com/inward/record.url?scp=85098241489&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85098241489&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-64375-1_22
DO - 10.1007/978-3-030-64375-1_22
M3 - Conference contribution
AN - SCOPUS:85098241489
SN - 9783030643744
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 627
EP - 656
BT - Theory of Cryptography - 18th International Conference, TCC 2020, Proceedings
A2 - Pass, Rafael
A2 - Pietrzak, Krzysztof
PB - Springer Science and Business Media Deutschland GmbH
T2 - 18th International Conference on Theory of Cryptography, TCCC 2020
Y2 - 16 November 2020 through 19 November 2020
ER -