Towards Non-Interactive Witness Hiding
Towards Non-Interactive Witness Hiding
复制标题
DOI：
10.1007/978-3-030-64375-1_22
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Benjamin Kuykendall;Mark Zhandry
中科院分区：
文献类型：
--
作者：
Benjamin Kuykendall;Mark Zhandry
证据隐藏要求验证者在看到证据后不能找到证据。到目前为止，证人隐藏证明所需的确切轮复杂度仍然是一个悬而未决的问题。在这项工作中，我们提供了令人信服的证据，证人隐藏证明是可扩展的非交互式的广泛的语言类。我们使用非交互式证人不可区分的证据作为我们所有协议的基础。在不同的假设条件下，我们给出了四个方案：一个通用的非交互式证明，只要任何证明系统，可能是一个低效的和/或非均匀的方案，是证人隐藏的，有一个已知的验证器运行时的界限，并有简短的可靠性证明;一个非均匀的非交互式协议，在最坏情况的复杂性假设下证明是证人隐藏的和有效的，但可能没有简短的可靠性证明。我们提出了一种启发式的方法来删除第一个消息，产生一个非交互式的论点。一个证人隐藏的非交互式证明系统的语言具有唯一的证人，假设不存在一个弱形式的证人加密的任何语言。
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 achievablenon-interactivelyfor 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:Auniversalnon-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.Anon-uniformnon-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 thetwo-message argumentof 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 withunique witnesses, assuming the non-existence of a weak form of witness encryption for any language in.