Efficient Batch Verification for UP
Efficient Batch Verification for UP
复制标题
UP 的高效批量验证
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Ron D. Rothblum
中科院分区：
文献类型：
--
作者：
Omer Reingold;G. Rothblum;Ron D. Rothblum
考虑这样一个设置：证明者想要说服验证者相信k个NP陈述的正确性。例如，证明者想要说服验证者k给定整数N1，…， Nk都是RSA模（即等长素数的乘积）。显然，这个问题可以通过简单地让证明者发送k个NP证人来解决，但这涉及到大量的沟通。互动能有所帮助吗？特别是，是否有可能为这个任务构建交互证明，其通信随k次线性增长？我们的主要结果是这样一个交互式证明，用于验证任何k个UP语句（即具有唯一见证的NP语句）的正确性。证明系统只使用一个常数的轮数，通信复杂度为kΔ·poly(m)，其中Δ > 0是一个任意小的常数，m是单个证人的长度，polyterm指的是一个只依赖于语言而不依赖于Δ的固定多项式。（诚实的）证明者策略可以在多项式时间内实现，给定对k（唯一）证人的访问。我们的证明利用了“交互式证人验证”（IWV），这是一种可能具有独立利益的新型证明系统。IWV是一个证明系统，其中验证者需要使用：(i)对所谓的NP证人进行次线性查询，以及（ii）与强大但不可信的证明者进行短暂交互来验证NP语句的正确性。与pcp和交互式pcp的设置相反，这里的验证者只能访问原始的NP见证，而不能访问其编码。
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 N1, ..., Nk 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Δ · poly(m), where Δ > 0 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 Δ. 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.