RSS订阅信息安全技术跟踪与研究:技术、平台、会议、论文、产业
你现在的位置:首页 / 技术积累 / 正文

52知识点之8:交互式证明与IP复杂度类

0 技术积累 | 2015年5月14日
转载申明:本站原创,欢迎转载。但转载时请保留原文地址。
原文地址:http://www.vonwei.com/post/8outof52.html

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

Posted by Bin Liu

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.

 

To answer the questions, we first 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

 

         本篇主要关注计算中交互的力量以及复杂度类IP。在计算复杂性理论内, IP是由交互式证明系统所能解决的一类问题。因此,首先介绍交互式证明系统。例如,目前所知的是,零知识证明在密码协议中具有重要的作用。交互式证明系统的概念最早是由Shafi GoldwasserSilvio Micali,和Charles Rackoff1985年提出的[1]。这样的证明有一个很迷人的性质,除了要证明断言的正确性不会泄露其他任何信息。为了达到这一点,Goldwasser等人在经典证明系统中增加了两个成分,开发出了交互式证明系统。第一个成分是随机化,对证明的验证可以是概率的,验证者Verifier被允许以很小的概率出错。第二个成分是交互,静态证明由动态的证明者prover所取代,证明在prover会和验证者Verifier交互让其相信断言的正确性。

 

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.

         什么是证明proof?简单地讲,一个证明是一种方式,通过这种方式一方让另一方相信某个断言是正确的。卷入到证明系统中的两方分别称为证明者prover和验证者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: 

  1. Efficiency: the      verification procedure can be carried out efficiently. 

  2. Soundness: for any true      assertion, there exists a proof. 

  3. Completeness: for any false      assertion, there exists no proofs. 

 

         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. 

         经典证明。一个经典的数学证明是一个固定的语句序列,这些语句序列可以全部由证明者prover所写,然后验证者Verifier可以很容易检测断言的正确性。这种方式的证明者和验证者之间没有交互。任何证明系统应该具有如下几个属性:(1)有效性:验证过程能有效地执行;(2)可靠性:对于任何正确的断言,都存在一个证明;(3)完备性:对于任何错误的断言,不存在任何证明。回顾复杂类NPNP可以视为一类语言,其成员都有证书,可以很容易被检测,而非成员没有证书。因此,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. 

         ExampleGraph 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:

ISO = {<G,H>|G and H are isomorphic graphs}

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.

         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}

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. 

         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.

         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 1/2.

         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.

交互式证明。在一个交互式证明系统中,证明者和验证者可以通过交换消息的方式进行相互交互。在介绍交互式证明这个概念之前,我们先给一个例子(来自文献[2])来说明交互在计算中的作用。

         例子,图的同构与非同构。两个图G的节点通过重组与图H一样,可以称为图G和图H同构。定义如下语言:

ISO = {<G,H>|GH是同构图}

很显然,ISO属于NP。即便节点数量会非常庞大,ISO的成员可以很容易进行验证(给出重构指令即可)。

         接下来考虑图的非同构,定义如下语言:

NOISO = {<G,H>|GH非同构图}

现在问题是,使用一个经典证明,一个证明者如何让一个验证者相信两个图不是同构的?我们并不知道如何提供简短的证明可以证明图是非同构的,验证者无法在多项式时间内检测所有的可能性。因此,我们不知道如何证明NOISO属于NP。不过,考虑下面的交互式协议可以完成这个需求。

         证明者和验证者的共同输入为一对图(G1,G2)。验证者随机选择一个比特b0或者1)和一个置换pi,然后将置换用到图Gb上获得图H。验证者然后将图H发送给证明者。接下来,证明者发送b’给验证者,当且仅当b=b’,验证者才accept

         这个协议背后的思想是,如果给定的图(G1,G2)不是同构的,那么证明者应该能够确定,H或者来自G1或者来自G2。不过,如果输入的两个图是同构的,即便拥有无限的计算能力,证明者最好的选择是给出一个随机猜测的b’,这种情况下,accept的概率最多1/2

         从如上例子可以总结,NOISO无法通过一个经典证明来完成,不过可以通过一个交互式协议来完成。由此可见交互在计算中的能量与作用。

         下面给出交互式证明和复杂度类IP的形式化定义。

 

Now we give the formal definition of interactive proofs and the complexity class IP

Interactive proof systemA 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:

  • Completeness(完备性)For      ever xL,  Pr[<P,V>(x)=1]≥2/3

  • Soundness(可靠性)For      every x?LPr[<P,V>(x)=1]≤1/3

 

The class IPThe class IP consists of all languages having interactive proof systems. 

 

         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]. 

         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]. 

         通过定义,明显可以看到,任何语言如果属于BPP,那么必定属于IP。如果我们将消息交互次数限制为1,那么可以确定NP也属于IP。实际上,IP是一个很大的类。在1992年,Shamir证明了PSPACE=IP [3]

 

[1] http://dl.acm.org/citation.cfm?id=63434

[2] http://www.amazon.co.uk/Introduction-Theory-Computation-Michael-Sipser/dp/0619217642

[3] http://dl.acm.org/citation.cfm?doid=146585.146609

[4] http://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol

 

英文原文博客地址:http://bristolcrypto.blogspot.co.uk/2014/12/52-things-number-8-how-does-interaction.html

 


  • ------------------分隔线----------------

  • 如果感兴趣,欢迎关注本站微信号,跟踪最新博文信息,手机微信扫一扫下面的二维码,即可关注!
  • 微月信公众号
  • 推荐您阅读更多有关于“ 52知识点   ”的文章

    请填写你的在线分享代码
    上一篇:52知识点之7:概率图灵机和BPP复杂类下一篇:[转]工业界VS学术界:一个年轻员工的视角

    猜你喜欢

    评论列表:

    发表评论

    必填

    选填

    选填

    必填,不填不让过哦,嘻嘻。

    记住我,下次回复时不用重新输入个人信息

    本站介绍
    最近发表
    本年最热文章
    本月最热文章
    网站分类
    文章归档