...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Efficient Batch Verification for UP
【24h】

Efficient Batch Verification for UP

机译：UP的高效批量验证

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Consider a setting in which a prover wants to convince a verifier of the correctness of k NP statements. For example, the prover wants to convince the verifier that k given integers N_1,...,N_k are all RSA moduli (i.e., products of equal length primes). Clearly this problem can be solved by simply having the prover send the k NP witnesses, but this involves a lot of communication. Can interaction help? In particular, is it possible to construct interactive proofs for this task whose communication grows sub-linearly with k?Our main result is such an interactive proof for verifying the correctness of any k UP statements (i.e., NP statements that have a unique witness). The proof-system uses only a constant number of rounds and the communication complexity is k^delta * poly(m), where delta0 is an arbitrarily small constant, m is the length of a single witness, and the poly term refers to a fixed polynomial that only depends on the language and not on delta. The (honest) prover strategy can be implemented in polynomial-time given access to the k (unique) witnesses.Our proof leverages "interactive witness verification" (IWV), a new type of proof-system that may be of independent interest. An IWV is a proof-system in which the verifier needs to verify the correctness of an NP statement using: (i) a sublinear number of queries to an alleged NP witness, and (ii) a short interaction with a powerful but untrusted prover. In contrast to the setting of PCPs and Interactive PCPs, here the verifier only has access to the raw NP witness, rather than some encoding thereof.
机译：考虑一种设置，在该设置中，证明者希望使验证者相信k个NP语句的正确性。例如，证明者想要说服验证者，k个给定的整数N_1，...，N_k都是RSA模（即，等长素数的乘积）。显然，只需让证明者发送k个NP证人即可解决此问题，但这涉及很多沟通。互动有帮助吗？特别是，是否有可能为此任务构造交互证明，使其通信与k呈亚线性增长？我们的主要结果是这种交互证明，用于验证任何k UP语句（即具有唯一见证人的NP语句）的正确性。 。证明系统仅使用恒定的轮数，通信复杂度为k ^ delta * poly（m），其中del> 0是任意小的常数，m是单个见证人的长度，poly项指一个仅取决于语言而不取决于增量的固定多项式。 （最诚实的）证明者策略可以在访问k个（唯一的）证人的情况下在多项式时间内实施。我们的证明利用了“交互式证人验证”（IWV），这是一种可能具有独立利益的新型证明系统。 IWV是一种证明系统，在该系统中，验证者需要使用以下各项来验证NP语句的正确性：（i）对所称NP证人的次线性查询，以及（ii）与功能强大但不受信任的证明者的短暂交互。与PCP和Interactive PCP的设置相反，此处的验证者只能访问原始NP见证人，而不能访问其某些编码。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号