多证明者交互式系统与单证明者交互式系统

使用空间有界证明器的罗尼特 鲁宾菲尔德普林斯顿大学计算机科学系乔·基利安NEC研究所Princeton，NJ 08540二○ ○九年五月二日摘要最近的结果在交互式证明系统[？[？[？]似乎表明在单个证明者交互式证明系统中的证明者比在多个证明者交互式证明系统中的证明者更容易欺骗验证者。我们表明，这是不是一个单一的证明，其中所有，但一个固定的多项式证明的空间被删除之间的每一轮的情况。这样做的一个结果是，任何多个证明器交互协议，其中证明器只需要多项式量的空间，可以很容易地转换成一个单一的证明器交互原型。col，其中证明器仅具有固定的多项式空间量。 这一结果还表明，一个可以很容易地转换跳棋[？]转换为自适应检查器[？在被检查的程序具有由固定多项式限定的空间的假设下。1介绍最近的结果表明，在复杂性理论IP=PSPACE [？[？]和MIP=NEXPTIME [？]. 这让我们有理由相信，在一个罪的力量有一个显着的差异验证者交互式证明系统与多个验证者交互式证明系统的能力，即由于多个证明者被限制为与每个证明者一致，由DIMACS支持，NSF-STC 88 -09648。[2]在麻省理工学院期间获得了NSF奖学金的支持。1另一方面，它们不能轻易地欺骗验证者，因此更困难的语言可以有这样的证明系统。已经表明，相同的语言集合被以下三种类型的交互式证明系统所接受：多证明者系统，单证明者系统，其中证明者被约束为根据预先固定的函数回答，以及单证明者系统，其中证明者的记忆在每个问题之间被擦除（即，证明者对对话没有记忆）。[？].有人可能会猜想，允许单个证明者系统中的证明者对对话有部分记忆，可以大大增加他作弊的能力，从而降低系统的能力。我们表明，这是不是这样的情况下：如果有一个交互式协议对一个证明者，不记得任何问题之间，那么对于任何s它可以被修改成一个交互式协议，对一个证明者，记得s位之间的问题。新协议的运行时间是原协议运行时间的多项式，且s。注意，IP证明器只需要记住轮之间的会话的历史，这是多项式数量的比特（然而，这里多项式是在协议决定之后而不是之前选择这一结果在密码学中有如下应用：它表明由两张信用卡实现的两个证明协议可以由一张信用卡实现，只要保证信用卡具有有限的内存。本文的结果也适用于程序结果检验[？] [？]. 他们展示了如何将一个假设程序是一个固定函数的检查器转换为一个自适应检查器，而不是假设程序具有多项式空间。 这是有趣的，因为它允许人们假设检查器工作，即使硬件故障随着时间的推移而演变，或者在软件编写的情况下，在某些输入上运行程序可能会对程序的未来行为产生意外的副作用。一个相关的结果[？如何自我纠正[？]空间有界测试程序中的一些函数这个结果只适用于函数是多项式，并没有显示如何给这些函数的程序结果检查器2定义我们非正式地描述了以下修改定义的交互式证明系统和IP [？]：定义2.1 s空间t轮交互协议（A，B）是一对共享输入带（只读）的图灵机（TM）（A，B）.两者都有一个私人读/写工作磁带和只读随机磁带。有两个通信磁带：一个是B只能写访问，A只能读访问，另一个是A只能写访问，B只能读访问。我们认为第一盘磁带包含了发送给A的信息，或者说是向A提出的“问题”，第二盘磁带包含了发送给A的信息，或者说是“答案”。到b 机器轮流工作，B先工作。 在每条信息之前对于A，擦除A的私有工作带的除了前s位之外的所有位。A是计算无界的，B是多项式时间有界的。定义2.2LetL∈{0，1}。我们说L有一个s-s空间群，如果存在一个TMV，使得1. 有一个TMPs.t. （P，V）是一个s-空间t-轮交互协议，对于所有x∈ L s.t.|X|足够大，Pr [V接受]> 2/3（当概率超过抛硬币P和V时）。2. 对于所有TM的P ′s.t. （P′，V）是一个s-空间t-轮交互协议，对所有x∈/Ls. |X|当概率大于P ′和V的抛硬币次数时，P[Vacc epts]=<1/3。我们称（P，V）是L的s-空间t-轮交互证明系统.定义IP（s，t）={L|L有一个S-P-R-O系统}我们可以认为P是决定性的，它给出最优的答案，以最大化V接受的概率PPP3主要定理定理1若L ∈ IP（0，t），则对所有s，L ∈ IP（s，O（st））.证明：我们证明了，如果存在一个0-空间，t-轮的交互协议L，那么我们可以构造一个S-空间O（st）-轮的交互协议L。对于L的0-空间，t-回合协议可以运行O（s）次，以便减少误差概率从1到12−s。 将得到的低错误协议称为CV，并令3名6名专业人员CV（w，r）=（x1，y1，. . . ，xm，ym）表示验证者V和证明者P之间的m轮对话，其中w是输入，r是验证者使用的随机字符串，xi是验证者发送给证明者的“问题”，yi是证明者发送给验证者的“答案”（注意m是O（st））.设Φ（w，r，CV（w，r））是验证者在转换后评估以决定是否接受或拒绝w的函数。让P表示一个可以通过两个问题来恢复的比特。我们现在准备好提交协议：s空间O（st）轮交互协议：在输入w上：1. 运行方案CV（w，r）=（x1，y1，. . . ，x m，y m）。如果Φ（w，r，CV（w，r））=PP然后拒绝并停止。2. 做3m次：选取i∈R[1，m]Verif ie r在x i上询问问题i，并在yi上接收答案。如果yi/=yi，则重新连接并停止。3. 接受w。s-空间O（st）-round协议的正确性证明：如果w∈L，则从我们的假设L ∈ IP（0，t）中可以明显看出，存在一个证明者P，它在每个问题之后只能记住s位，使得Pr r [Φ（w，r，CV（w，r））=“ACCEPT”] ≥ 2 / 3。为了证明w不在L中的情况下的定理，我们需要证明，能够记住s位的证明者不可能欺骗验证者接受L。PP6≤˜˜P666我们首先注意到，在任何空间上，P_i都可以按以下方式被看作是2s函数s的集合：考虑具有2s状态的确定性有限状态自动机，其中每个状态i都被标记为函数P_i。函数之间的转换被标记为验证者可以向证明者提出的所有可能的问题然后证明者处于2s状态之一，并且每当验证者提出问题时，证明者根据标记状态的函数回答问题，并根据应用于当前状态的转移函数和验证者刚刚提出的问题进入新的状态对于固定的i，如果Φ（w，r，CVi（w，r））=“ACCEPT”（其中证明者P i是根据函数P i回答的证明者），我们说r是Pi-bad forw由于C Vi是L的0-空间交互协议，误差为12 −s，我们知道r是P i-bad，具有相同的概率。我们认为，如果存在这样的假设，则r对于w是Pi-坏的，则r对于w是Pi-坏的W. 如果在ly2sP is上存在r，则Pr[r是P−badforw]≤2s·12−s=1。对于每个r，以下三种情况之一必须成立1. Φ（w，r，CV（w，r））=P2. r是P-badforw。通过以上分析，出现概率≤1/6的情况。3. Φ（w，r，CV（w，r））=“A C C E PT”，但r对w不是P-坏的。为了我们所有人，PΦ（w，r，C）Vi（w，r）=（a1，b1），. . . ，（a m，b m））=“RESTING”。然后对于所有i，thereisajsuchthatxj=ajbutyj=/bj（因为 conversations不能相同，并且验证者遵循相同的算法，所以第一个差异必须来自证明者）。因此，无论证明器在本发明的步骤2的循环期间处于哪种状态，对于满足yj/=ymj的情况 ，问题被确定的概率至少为1/m。在3m次之后，验证者不拒绝的概率至多为e −3。因此，如果w不在L中，验证者将以至少1−1−e−3≥2/ 3的概率拒绝4S-空间证明器的能力边界定理证明中用到的变换？？仅适用于确定性证明者，因为合法的概率性证明者可能会导致验证者在步骤2中拒绝，对问题给出前后矛盾的答案 人们可以用“最优”确定性证明器来替换任何概率性证明器，但是这个新的证明器可能具有更大的计算要求。因此，这样一个简单的修复将不允许我们将结果结转到程序结果检查。然而，我们可以使用定理证明中使用的一般思想？？直接限制了s-空间有界证明器相对于0-空间有界证明器的优势我们的定理如下：1[1]这个结果是由Lund独立发现的（个人交流）。0我我3定理2假设在一个交互式协议（P，V）中，证明者的记忆最多被部分擦除t次.设P s是允许在部分擦除之间记住s位的证明器，并且设P0是不允许在擦除之间记住任何位的最优证明器。对于所有的x，Pr[（Ps，V）接受x]stPr[（P，V）接受x] ≤2。证明：我们假设Ps是确定性的，并且用p表示（Ps，V）接受x的概率。我们现在构造一个0-空间有界证明器P0，使得（P0，V）以至少2−stp的概率接受x。P0的工作原理与Ps完全相同，只是每当它的内存被（完全）擦除时，它会将内存的前s位设置为随机的s位串。假设（Ps，V）在V使用r作为其随机输入时接受它足以表明，当V使用r作为其随机输入时，（P0，V）将以概率2−st接受令Sr表示在第i次（部分）存储器擦除之后Ps的存储器的前s位的内容在概率为2−st的情况下，对于每个i，1≤i≤t，P0将在第i次内存擦除后用Sr填充其内存无论何时发生这种情况，P0的行为将与Ps的行为相同，V将接受。因此，只要（Ps，V）接受，（P0，V）将以至少2−st的概率接受，定理如下。因此，任何协议，它实现了一个足够低的错误概率，使用足够少的内存擦除，自动鲁棒性对s-空间有界证明，无需修改。因此，给定一个对0-空间有界证明器鲁棒的交互式证明系统，只使用t个内存擦除，只需要将错误概率降低到小于1·2-st，同时保持内存擦除的总数5致谢我们要感谢迪克·利普顿提出这个问题。我们还要感谢Uri Feige、Shafi Goldwasser、Diane Hernek、Hugo Krawczyk和Mike Luby就这个主题进行了非常广泛和有益的讨论，并对本文提出了有益的意见引用[1] 巴巴伊湖福特诺湖隆德角，“非确定性指数时间具有两个验证器交互协议”，技术报告90-03，芝加哥大学，部门。计算机科学也在1990年第31届计算机科学中。[2] Ben-Or，M.，Goldwasser，S.，Kilian，J.，和Wigderson，A.，[3] Ben-Or， M.， Goldwasser， S.， Kilian， J.， 和 Wigderson， A.， “Multi-ProverInteractive Proofs ： How to Remove Intractability Assumptions” ， Proc. 20th ACMSymposium on Theory of Computing，1988，pp. 113-131.[4] 布鲁姆，M.，[5] 布 鲁姆 ，M.， Kannan，S.，以 及检查其工 作的程序设计 ” ，Proc.21st ACMSymposium on Theory of Computing，1989。[6] 布鲁姆，M.，卢比，M.，Rubinfeld，R.，[7] 布鲁姆，M.，卢比，M.，Rubinfeld，R.，“针对自适应程序和密码设置的程序结果检查”，分布式计算和密码学，离散数学和理论计算机科学中的DIMACS系列，卷。1991年2月。[8] 费奇大学，[9] 福特诺湖Rompel，J.，Sipser，M.，“On the Power of Multi-Prover InteractiveProtocols”, 第三届复杂性理论会议，1988年，pp。156- 161。[10] Gemmell，P.，利普顿河，Rubinfeld，R.，Wigderson，A.，[11] Goldwasser，S.，Micali，S.，Rackoff，C.，交互式证明系统的知识复杂性”，SIAM J。，18（1），1989，pp. 186-208.[12] 隆德角，福特诺湖Karloff，H.，Nisan，N.，[13] Shamir，Adi，