标签：what interaction help 验证 IP prover 证明 verifier proof

52 Things: Number 8: How does interaction help in computation, and what is the class IP?

52 件事：数字 8：交互如何帮助计算，什么是类 IP？

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. This blog post concentrates on the power of interaction in computation and the Complexity Class IP
这是一系列博客文章中的最新一篇，旨在解决“每个博士生都应该知道的 52 件事来做密码学”列表：一组问题汇编，让博士生在第一年结束时了解他们应该知道什么。这篇博文重点介绍了交互在计算和复杂度等级 IP 中的强大功能. To answer the questions, we first give give a brief introduction of the interactive proof systems. As we know, zero-knowledge proofs currently play an important role in the study of cryptographic protocols. This concept was introduced by Goldwasser, Micali and Rackoff in [1]. Such proofs have the fascinating property of revealing nothing other than the validity of assertions being proven. In order to achieve this, Goldwasser, Micali and Rackoff developed the interactive proof systems by adding two ingredients to the classical proof systems. The first ingredient is randomisation, the verification of proofs can be probabilistic and the verifier is allowed to err with small probability. The second one is interaction, the static proof is replaced by dynamic prover who will interact with the verifier to convince it the assertion is true. Combining the classical proof systems with the two ingredients has a huge effect: the set of languages of interactive proof systems is in a large complexity class IP.
为了回答这些问题，我们首先对交互式证明系统进行简要介绍。众所周知，零知识证明目前在密码协议的研究中发挥着重要作用。Goldwasser、Micali 和 Rackoff 在 [1] 中引入了这个概念。这种证明具有令人着迷的特性，即除了被证明的断言的有效性之外，别无他物。为了实现这一点，Goldwasser、Micali 和 Rackoff 通过在经典证明系统中添加两种成分来开发交互式证明系统。第一个要素是随机化，证明的验证可以是概率性的，并且允许验证者以很小的概率出错。第二个是交互，静态证明被动态证明者所取代，动态证明者将与验证者交互以说服它断言是正确的。将经典证明系统与这两种成分相结合会产生巨大的影响：交互式证明系统的语言集处于大复杂度等级 IP 中。 What is a proof? 什么是证明？ Loosely speaking, a proof is a way for a party to convince another party that a certain assertion is true. The two parties involved in a proof system are called a prover and a verifier.
粗略地说，证明是一方说服另一方相信某个断言是正确的一种方式。参与证明系统的两方称为证明者和验证者。 Classical proofs 经典证明 A classical mathematical proof is a fixed sequence of statements, which can be all written down by the prover then the verifier can easily check the validity of the assertion. There is no interaction between the prover and the verifier.
经典的数学证明是一个固定的语句序列，这些语句可以全部由证明者写下来，然后验证者可以很容易地检查断言的有效性。证明者和验证者之间没有交互。 Any proof system should have the following properties:
任何证明系统都应具有以下属性：

Efficiency: the verification procedure can be carried out efficiently.
效率：验证程序可以高效执行。
Soundness: for any false assertion, invalid proofs are hard to find.
合理性：对于任何错误的断言，都很难找到无效的证据。
Completeness: for any true assertion, there exists a proof.
完整性：对于任何真实的断言，都存在一个证明。

Recall the complexity class NP can be viewed as a class of languages whose members all have certificates that can be easily checked (the non-members do not have certificates). Hence we have NP is exactly the class of languages of classical proofs.
回想一下，复杂度类 NP 可以看作是一类语言，其成员都具有可以轻松检查的证书（非成员没有证书）。因此，我们有NP正是经典证明的一类语言。 Interactive Proofs 交互式证明 In an interactive proof system, the prover and verifier are allowed to interact with each other by exchange of messages. Before introducing the concept of interactive proofs, we first give an example (which can be found in [2]) to show how does interaction help in computation.
在交互式证明系统中，允许证明者和验证者通过交换消息进行交互。在介绍交互式证明的概念之前，我们首先给出一个示例（可以在 [2] 中找到）来说明交互如何帮助计算。 Example: Graph Isomorphism and Graph Non-isomorphism.
示例：图同构和图非同构。 Two graphs G and H are called isomorphic if the nodes of G can be reordered so that it is identical to H. We define the language:
如果 G 的节点可以重新排序，使其与 H 相同，则两个图 G 和 H 称为同构图。我们定义语言： ISO = {<G,H>|G and H are isomorphic graphs}
ISO = {<G，H>|G 和 H 是同构图} It is clear that ISO is in NP. Even though the number of nodes can be very large, the membership of ISO can be easily verified by given the instructions of reordering.
很明显，ISO 在 NP 中。尽管节点数量可能非常大，但可以通过给出重新排序的指令轻松验证 ISO 的成员资格。 Then we consider the complement problem of Graph Isomorphism, namely Graph Non-isomorphism. We define the language:
然后我们考虑图同构的补码问题，即图非同构。我们定义语言： NOISO = {<G,H>|G and H are not isomorphic graphs}
NOISO = {<G，H>|G 和 H 不是同构图} And the question is, using a classic proof, how can a prover convince a verifier that two graphs are not isomorphic? We don't know how to provide short proofs that the graphs are not isomorphic and the verifier can't check every possibilities in polynomial time. Thus, we don't know how to prove that NOISO is in NP. Nevertheless, consider the following interactive protocol, the prover can convince the verifier the fact that the given two graphs are not isomorphic.
问题是，使用经典证明，证明者如何说服验证者两个图不是同构的？我们不知道如何提供简短的证明，证明图不是同构的，验证者无法在多项式时间内检查所有可能性。因此，我们不知道如何证明 NOISO 在 NP 中。尽管如此，考虑以下交互式协议，证明者可以说服验证者给定的两个图不是同构的。
Both the prover and the verifier have a pair of graphs (G1,G2) as common input. The verifier randomly choose a random bit b∈{0,1} and a permutation π. Then it applies π on Gb to get a graph H. The verifier sends H to the prover. Next, upon received H, the prover sends b′∈{0,1} to the verifier. Finally, the verifier accepts if and only if b′=b.
证明者和验证者都有一对图形 (G1,G2) 作为公共输入。验证器随机选择一个随机位 b∈{0,1} 和一个排列 π 。然后它适用于 π Gb 获取图形 H 。验证程序发送给 H 验证者。接下来，在收到 H 后，证明者将发送给 b′∈{0,1} 验证者。最后，验证者接受当且仅当 b′=b .
The idea behind the protocol is, if the given graphs (G1,G2) are not isomorphic, then the prover should be able to identify H is from either G1 or G2. However, if the input graphs are isomorphic, even with unlimited computational power, the best choice of the prover is to make b′ a random guess. In this case, the prover accepts at most 12.
该协议背后的思想是，如果给定的图 (G1,G2) 不是同构的，那么证明者应该能够识别 H 来自或 G1 G2 。但是，如果输入图是同构的，即使具有无限的计算能力，证明者的最佳选择也是 b′ 随机猜测。在这种情况下，证明者最多 12 接受 .
From the above example, we conclude that NOISO cannot be proved to the verifier via a classic proof, whereas it could be proved via an interactive proof(protocol). We can see there is some power in interaction.
从上面的例子中，我们得出结论，NOISO不能通过经典证明向验证者证明，而可以通过交互式证明（协议）来证明。我们可以看到互动中有一些力量。
Now we give the formal definition of interactive proofs and the complexity class IP.
现在我们给出交互式证明的正式定义和复杂度等级 IP。
Interactive proof system: A pair of interactive machines (P,V) is called an interactive proof system for a language L if machine V is polynomial-time and the following conditions hold:
交互式证明系统：如果机器 V 是多项式时间并且满足以下条件，则一对交互式机器 (P,V) 称为语言 L 的交互式证明系统：

Completeness: For ever x∈L,
完整性：永远 x∈L ，

Pr[<P,V>(x)=1]≥23

Soundness: For every x∉L
健全性：适用于每个 x∉L

Pr[<P,V>(x)=1]≤13
The class IP: The class IP consists of all languages having interactive proof systems.
IP类：IP类由具有交互式证明系统的所有语言组成。
By the definition, it is obvious that any language in BPP is in IP. And if we restrict the exchange of messages between the machines to be 1, then we have NP is in IP. Actually, IP is a surprisingly large class. In 1992, Shamir revealed that PSPACE=IP [3].
根据定义，很明显，BPP中的任何语言都是IP语言。如果我们限制机器之间的消息交换是 1 ，那么我们有 NP 在 IP 中。实际上，IP是一个令人惊讶的大类。1992年，Shamir揭示了PSPACE=IP [3]。 In addition, notice that in the protocol, the prover has the ability to toss a private-coin. If the prover is allowed to access to the verifier's random string leads to the model of interactive proofs with public-coins, which is related to a similar complexity class AM [4].
此外，请注意，在协议中，证明者能够抛出私有币。如果允许证明者访问验证者的随机字符串，则会导致与public-coins交互式证明的模型，这与类似的复杂度等级AM [4]有关。

标签：what,interaction,help,验证,IP,prover,证明,verifier,proof
From： https://www.cnblogs.com/3cH0-Nu1L/p/18104684

52 Things: Number 8: How does interaction help in computation, and what is the class IP?

52 Things: Number 8: How does interaction help in computation, and what is the class IP?

相关文章

赞助商

阅读排行