交互式证明系统的复杂性与有界通信

1用简洁证明器实现交互式证明Oded Goldreich<$Salil Vadhan和Avi Wigderson§2003年2月11日摘要我们继续调查的互动证明与有界通信，开始由Go ldrei ch和dHastad（IPL1998年）。 LetL是一种语言，它具有一种独特的行为，其中前向验证器提供几个（几个）位。我们假设补语L有常数-循环交互式证明的复杂性，只依赖于指数b。这提供了第一个证据，对于NP完全语言，我们不能期望交互式证明器比标准NP证明更当证明系统被进一步限制时（例如，当b = 1时，或者当我们有完美的复数时），我们在L的复数上得到更好的上界。关键词：交互式证明系统，亚瑟-梅林游戏，NP，采样协议，统计零知识，博弈论本论文的扩展摘要发表在Proc. of the 28 th ICALP，Springer's LNCS 2076，pages 334-345，Crete，Greece，July2001中†省计算机科学，魏茨曼研究所的科学（Rehocket，ISRAEL）.电邮地址：oded@wisdom.weizmann.ac.il. 网址：http://www.wisdom.weizmann.ac.il/ 由MINERVA支持基金会，德国。哈 佛大学工程与应用科学系（美国马萨诸塞州剑桥）。电子邮件：salil@eecs.harvard.edu。网址：http://eecs.harvard.edu/www.example.com在新泽西州普林斯顿高等研究所完成的工作，由NSF数学科学博士后研究奖学金支持。§高等研究所（美国新泽西州普林斯顿）和希伯来大学计算机科学研究所（以色列耶路撒冷）。电子邮件：avi@ias.edu。部分由NSF资助CCR-9987845和CCR-9987077支持。1内容1介绍21.1关于有界交互的交互式证明的先前工作21.2关于有界交互的交互式证明的新结果31.3相关工作41.4组织和技术52第五章2.1符号52.2有界交互的交互式证明2.3统计零知识（SZK）72.4概率可检验证明（PCP）73结果的正式声明3.1仅发送一位的证明器83.2关于只发送一条消息的证明者83.3关于发送有界位数的证明器93.4关于发送有限数量消息的证明器94论极其简洁的证明者（只说一个位）105关于发送一条信息的简洁证明者5.1接受概率-唯一答案135.2接受概率-一般情况166关于具有完全完备性的简洁证明器187关于一般的简洁证明者197.1议定书的动机7.2第22章真正的7.3分析248消息复杂性层次结构279进一步工作的方向基准30附录30已知基数的抽样集B 关于定理2.3的一些评论32B.1基本开关（从MA到AM）32B.2游戏中期的并发切换（[MAMA]r到[AMMA]r= [AM]rA）33B.3A direct approach（to placing（AM）r in AM）（将（AM）r置于AM中的直接方法）3421介绍交互式证明系统是由Goldwasser，Micali和Rackoff [？]，以便捕捉一方可以有效地验证另一方更强大的一方所提出的主张的最一般的方式。也就是说，交互式证明系统是两方随机协议，通过该协议，计算无界的证明者可以说服概率多项式时间验证者以预定语言的公共输入的成员资格。因此，交互式证明系统概括并包含传统的“NP证明系统”（其中验证是确定性的和“非交互式的”）作为特例。众所周知，这种推广给我们带来了很多：Lund，Fortnow，Karloff，Nisan和Shamir的IP特征定理[？、、怎么样？]指出PSPACE中的每一种语言都有一个交互式证明系统（很容易看出只有PSPACE中的语言才有交互式证明系统）。众所周知，交互式证明的强大表现力很大程度上是由于交互的存在特别是，发送单个消息的交互式证明（如NP证明）产生的复杂性类（称为MA）似乎非常接近NP。 探索在无限交互和无交互这两个极端之间会发生什么是很有趣的。也就是说，什么是交互式证明的表达能力，利用有限的，但非零，互动量？1.1关于有界交互交互式的证明与几个消息。对上述问题的最早调查研究了交互式证明的消息复杂性，即，交换的消息数。（有时，我们指的是轮，这是一对验证者-证明者消息。Babai和Moran的加速定理[？]（连同[？]）表明交互式证明中的消息数量总是可以减少一个常数因子（假设消息数量至少保持为2）。另一方面，有一个常数轮交互式证明和无限制的交互式证明之间的差距很大如上所述，所有的PSPACE都有一个通用的交互式证明[？] 、、怎么样？].相比之下，AM类的问题与常数轮交互式证明被认为是相对接近NP。具体来说，上午在于第二层次的多项式时间层次[？]，不能包含coNP，除非多项式时间层次崩溃[？]，实际上等于NP下合理的电路复杂性假设[？、、怎么样？、、怎么样？].简洁的证明者。一个更精细的调查上述问题是由Goldreich和Hastad[？[1]，他致力于语言的复杂性，在使用的通信比特数（和/或随机性）上具有他们考虑的限制之一，也是我们研究的主要焦点，是通过一些约束b来限制从证明者发送到验证者的比特数。也就是说，什么语言可以被“简洁”的证明者证明由于证明者试图向验证者传达一些信息，这似乎是最具交互性的沟通方向此外，对于交互式证明的应用（例如， 在密码学协议中），它对其中在一个方向上通信更昂贵的常见情况进行建模（例如，如果证明器是手持无线设备）。1亚瑟-梅林游戏，由Babai介绍[？]，是交互式证明的一种特殊类型，其中验证者被限制发送它投掷的每个硬币的结果。这样的证明系统也被称为公共硬币，并被称为一般的交互式证明表达[？] ]. 我们警告后一个断言指的是整个类，而不是精确的复杂度测量，例如由证明器发送的比特总数（下面考虑）。3·⊆·⊆∩一方面，我们知道几个“硬”问题的交互式证明（例如，二阶的N ONRESIDUOSITY[？]，G N单同构[？]，和其他[？、、怎么样？、、怎么样？]），其中从证明者到验证者的通信是严格受限的（实际上，受限于一位）。 另一方面，没有这样的证明系统是已知的NP完全问题，也没有任何迹象表明不可能（除了当额外的限制强加[？]）. 在这项工作中，我们为不可能性提供了强有力的证据。1.2有界交互作用我们的主要重点是简洁的证明者，也就是说，在交互式证明中，由证明者发送的位的总数是有界的。简洁的证明者。 考虑交互式证明，其中证明者在长度为n的i个点上向验证者发送最多b = b（n）个比特。 Gol drei c h和Hastad[？，Thm. [4]在BPTIMENP（T）中，T = poly（n）2 poly（b），这显然对NP中的语言没有任何意义。相比之下，我们证明了这种语言的补语具有复杂度T的常数轮交互式证明（即，验证者的计算时间和总通信由T限定）。特别地，NP完全问题不能有交互式证明，其中证明者向验证者发送多多项式的许多比特，除非coNP在AM的准多项式模拟中。事实上，假设NP具有常数轮的交互式证明与对数证明者到验证者的通信，我们得出结论coNP AM。如上所述，这是极不可能的。我们在两种特殊情况下得到更强的结果：1. 我们证明，如果一种语言有一个完美完备性的交互式证明（即，在是实例上的零错误概率），其中证明器发送最多b（n）个比特，则它在coNTIME（T）中，其中T（n）= 2 b（n）poly（n）。因此，除非NP=coNP，NP完全语言不能有完美完备的交互式证明系统，其中证明者发送了许多位。2. 我们表明，如果一种语言有一个交互式的证明，其中证明者发送一个单一的位（有一些限制的错误概率），那么它有一个统计零知识的交互式证明，也就是说，在类SZK。这是一个比我们的主要结果更强有力的结论。是coAM，如前所述[？[ndAielloand ndH？]. ”““记得Sahai和Vadhan吗？]表明SZK中的任何语言都有一个交互式证明，其中证明者发送一个比特，我们得到了这两个类之间令人惊讶的等价性。交互式的证明与几个消息。我们获得了一个（显然）关于消息复杂性的新结果。前面提到的结果留下的一个问题是在常数轮和多项式多轮之间发生了什么换句话说，Babai和Moran的加速定理是否可以改进，以表明对于某些mj=o（m），m（n）-消息交互式证明可以被mj（n）-消息交互式证明模拟（因此并不比MJ（n）-消息交互式证明更强大）？通过结合仔细的参数化[？、、怎么样？]和[？]，我们观察到这样的改进加速是不可能的。 更确切地说，对于每个好的函数m，我们证明了存在一种语言，它具有m（n）-消息交互式证明，但不是o（m（n））-消息交互式证明，只要#SAT不包含在coAM的次指数模拟中。4·∩1.3其他相关工作我们注意到了Gol drei c handHastad[？当对交互式证明施加进一步的限制时，如果我可以用简洁的证明者对交互式证明进行强有力的证明，则已经给出了特别是，他们获得了BPTIME（T）（而不是BPTIMENP（T））的上界，T= 2poly（b） poly（n），对于具有以下任何一种交互式证明的语言：（1）公共硬币证明，其中证明者发送最多b位，（2）证明，其中双向通信以b为界。多证明器交互式证明和PCP。低通信的多证明者交互证明（MIP’s）和概率可检验证明（PCP’s）的表达能力许多研究的动机是在MIP/PCP的应用程序中的通信参数的重要性，以不可逼近。特别是，Bellare，Goldreich和苏丹[？] ]给出了关于“简洁”PCP和MIP的表达能力的否定结果由于一个查询PCP交互式证明的知识复杂性。我们的工作也与知识复杂性有关。知识的复杂性，提出了[？]，旨在衡量在交互式证明中有多少 Goldreich和Petrank [？]，和一系列的工作提供了上界的复杂性的语言具有交互式证明与低知识复杂性（见[？、、怎么样？]的结果，关于知识的复杂性和[？、、怎么样？、、怎么样？[关于替代概念的结果这些结果与我们的结果有关，但不能相比。例如，Petrank和Tardos [？]证明了知识复杂度k =O（log n）的语言都包含在AM coAM中。虽然交互式证明的知识复杂性确实受到证明者到验证者通信量的限制，但他们的结果并没有产生任何有趣的简洁交互式证明。原因是他们的结果只适用于错误概率显著小于2−k的交互式证明，很容易看出证明者到验证者通信k=O（logn）且错误概率显著小于2−k的交互式证明只捕获BPP（因此是无趣的）。相比之下，我们的结果适用于恒定的错误概率。Sahai和Vadhan [？]（改善[？[]）表明，具有对数知识复杂性的语言在“提示意义”上坍缩为SZK，并且即使错误概率为常数，他们的结果也适用。然而，这也是我们无法比拟的，因为“提示感”是知识复杂性的一个度量，它不受证明者到验证者通信的限制。（事实上，“暗示意义”的提法被认为是知识复杂性的一个令人满意的定义，由Goldreich和Petrank [？]由于上述及相关问题。然而，“暗示意义”上的知识复杂性计算机声音交互式证明。最后，重要的是要注意，情况是显着不同的论点系统[？[1]（也称为计算可靠证明）。这些就像交互式证明，但可靠性条件仅限于多项式时间证明器。基 利 安[？]表明，NP有简洁的论点系统，如果强抗碰撞哈希函数存在。具体来说，在一个足够强（但仍然可信）的假设下，NP具有公共硬币参数，其中验证者的随机性和双向通信是多对数的。 结合[？]，这提供了一个强大的分离效率之间的5±NP的论证与交互式证明。我们的结果将这种分离扩展到只计算证明者到验证者通信的情况（并且交互式证明不需要是公共硬币）。1.4组织和技术在第2节中，我们回顾了一些相关的定义，符号和以前的工作结果 使用这些符号，在第3节中，我们陈述我们的结果并将其与先前的工作进行比较。 进一步研究的方向在第9节中提出。在第4节和第5节中，我们研究了只发送一条消息（甚至一个比特）的简洁证明者这些部分的主要技术贡献是各种形式的证明系统之间的一系列简化，最终结果是统计零知识证明系统。在第6节中，我们考虑完美完备性的简洁证明 我们减少这样的证明系统的分析，在博弈论的经典结果。本文的主要结果在第7节中得到证明主要的技术贡献是一个证明系统，用于证明一个（相当严格的）下界的总和指数许多（例如， 2 n）quanities，其中每个数量都很容易验证。基本思想是根据它们的近似大小对这些量进行聚类，随机选择几个聚类（概率与聚类的“权重”成比例），并通过适当的协议对每个选定的聚类进行我们强调，这个证明系统的新颖性在于建立了相当严格的下限（例如，紧到一个系数10（1））而不是许多偏离大得多的因子的下限（例如， 因子n）。在第8节中，我们提出了一个消息复杂度层次（基于合理的推测，garding#SAT）。 结果如下立即从改进版本的已知结果;具体来说，交互式证明#SAT沙米尔[？]（继[？]）和Babai和Moran [？].2预赛我们假设读者熟悉交互式证明（和公共硬币交互式证明）的基本概念;参见，例如，[怎么样？、、怎么样？、、怎么样？]. 在整个过程中，我们使用的是Promise问题的交互式证明，而不是语言。一个promise问题<$=（<$Y，<$N）是一对不相交的字符串集合，分别对应于YES和NO实例换句话说，承诺问题就是一个简单的决策问题，其中排除了一些输入交 互 式证明的定义被扩展到自然的承诺问题：我们要求当输入是一个是的实例时，证明者说服验证者以高概率接受（完整性）;当输入是一个否的实例时，验证者以低概率接受，无论证明者遵循什么策略（可靠性）。使用promise问题而不是语言只会使我们的结果更强（定理4.5的一个方向除外）。2.1符号我们表示为IP（b，m）（分别，AM（b，m））具有交互式证明的问题类（分别为，公共硬币交互式证明），其中证明者发送总共至多B比特，并且交换的消息的总数（在两个方向上）至多为M。注意，b和m是公共输入长度的整数函数，表示为n。当b不是n中的多项式时，可以理解，我们讨论的是一种推广，其中允许验证者在b中是时间多项式，6⊆ ⊆⊆n（而不是只在n中）。 除非另有说明，否则我们指的是具有完备性概率2/3和可靠性概率1/3的证明系统。我们表示IP（b）=IP（b，2b）;也就是说，只对交换的消息数进行平凡的限制当证明系统具有完美完备性时，我们用IP+IP的类似物表示（即，概率1）。具有常数轮交互式证明的问题类是denotedAMd=efAM（pol y（n），2）=IP（pol y（n），O（1））. （第二个等式是由等式2.3和2.4给出的。（见下文第4段）当我们希望指定完整性概率c=c（n）和可靠性概率s=s（n）时，我们将使用下标：IPc，s和AMc，s。 除非另有说明，我们总是假设t h在c（n）>s（n）+1/pol y（n）。2.2有界交互使用上述符号，我们回忆一些与我们的研究相关的结果我们的起点。Go ldrei ch和Havastad的主要结果是我们工作的起点（和参考点）。定理2.1（[？]） AM（b，m）-BPTIME（poly（2 b，m，n））定理2.2（[？]） IP（b，m）-BPTIME（poly（2 b，mm，n））NP定理2.1仅仅是为了透视而陈述的。我们的结果与定理2.2有关，并改进了定理2.2（它涉及一般的交互式证明，而不是公共硬币的证明）。 我们强调，从一般的交互式证明到公共硬币证明的转换（见定理2.4）并不保持证明者发送的比特总数。事实上，非常简洁的证明者（即，其中证明器发送单个比特）对于几个问题是已知的，这些问题被广泛认为不加入BPP（这类问题的例子包括Q阶N ONRESIDUOSITY[？]，GN同构[？]，D ISCRETE L OGARITHM P PROBLEM[？].）使用的结果。我们将使用已知结果的一些（参数化）扩展。除了定理2.3中的第二个包含（在附录B中证明），所有的扩展（或参数化版本）都是直接从相应的原始工作。定理2.3（加速定理[？]）AM（b，m）=AM（b2·pol y（m），[m/2|）n=（（b·m）O（m），2）.定理2.4（IP [？]的AM仿真） IP（b，m）-PAM（poly（b，n），m +1）.定理2.5（[？]） 如果coNPAM（b，2），则n =2 n =2（poly（n，b））。特别地，如果coNP AM，则多项式时间层次崩溃为PH = 102= 102。在本文的上方和全文中， i（t（n）表示由t（n）时间交替图灵机接受的一类问题，其中i个交替以存在性（分别，非对称）量化器。因此，dkid=efi（poly（n））和dkid=efi（poly（n））构成多项式时间层次的第i层7|∈−∈|--≥≥| || || |||log（c/s）2.3统计零知识（SZK）我们还将考虑SZK，一类拥有统计零知识交互式证明的问题。在这里，我们将不回顾SZK的定义，而是使用SZK在完整问题方面的最新特征对于分布X和Y，令（X，Y）表示它们的统计差异（或变化距离，即， X（X，Y）=maxS Pr [X S] Pr [Y S]）。 我们考虑的分布指定的电路，从他们的样本。 更准确地说，具有m个输入门和n个输出门的电路可以被看作是对0， 1n通过对m个随机输入位评估电路而引起承诺问题SD=（SDY，SDN），其中SDY={（X，Y）：<$（X，Y）≥2/3}SDN={（X，Y）：n（X，Y）≤1/3}，统计差异是其中X和Y是由从它们采样的电路指定的概率分布更一般地说，对于任何1α>β0时，我们将计算SDα、β的变化，其中2/3和1/3的三个窗口分别用α和β表示。定理2.6（SZK [？]的完全问题） 对于任意常数1> α2> β > 0，SZK的SDα，β问题是完全的.也就是说，SDα，β在SZK中，并且SZK中的每个问题都可以通过多项式时间（多1）约简而约简为SD α，β。因此，不是将某些问题放在类SZK中（分别是，表明SZK具有某些交互式证明），我们可以将这些问题简化为SD（分别，显示SD具有这样交互式证明）。2使用的其他结果。 以下关于SZK的结果也与我们相关：定理2.7（[？，？]）SZKPRAYAMPRAYCOAM.定理2.8（[？]）SZK在complement下是封闭的。定理2.9（[？]）SZKIP1−2−n，1/2（1）.2.4概率可检验证明（PCP）正如在引言中所述，我们的一些结果可以用概率检验的证明来看待不严格地说，一个概率可检验的证明系统由一个概率多项式时间验证器组成，它可以访问一个以冗余形式表示证明的预言。通常，验证者只访问几个预言位，这些位的位置由验证者掷硬币的结果决定对于完整性和可靠性界限c和s，要求验证者以至少c（x）的概率接受任何是实例x（即，当被给予对适当的预言机的访问时），而不管使用哪个预言机，它都以至多s（x）的概率接受任何NO实例x只要这一点成立，并且如果验证者最多使用r（x）个随机比特，最多进行q（x）个布尔查询，我们就说问题出在PCPc，s（r，q）中。对于数学上有界的q，我们也可以说这个问题已经分摊了查询复杂度q，并且表示具有摊销查询复杂度q（和随机性）的问题的类2复杂度r），通过PCP（r，q）。（关于这些概念的进一步讨论，见[？].）这将是有趣将我们的结果与以下已知结果进行对比2这里我们使用SZK在多-一约化下封闭的事实[？].8≤..ΣΣ定理2.10（第二节）10.2 in [？]）1. PCPc，s（poly（n），1），对于任何函数c，s。2. PCP（O（log n），1 − k）k P，对于每个常数k> 0。我们还考虑了PCP系统的空闲比特复杂度不严格地说，这里区分验证者将答案与由先前获得的答案确定的值进行比较的查询，以及验证者仅记录答案以供将来使用的查询。后一种查询被称为自由查询（因为它们的用FPCPc，s（r，f）表示一类具有PCPc，s（r，q）-系统的问题，其中至多fq个查询是自由的.定理2.11（第二节）10.3 in [？]） FPCP1，s（poly（n），0）≠ NP，对于任何函数s <1.3结果的正式声明我们改进了定理2.2，并解决了[？、Sec.3]。我们的主要结果如下。3.1只发送一位的证明器对于一个比特的证明者到验证者的通信，我们获得了到SZK的崩溃。定理3. 1F或c，s的每一个p，使得1>c2>s>c/2>0，IPc，s（1）=SZK。从五氯苯酚系统的角度来看，这意味着对于任何1> c2> s> c/ 2> 0，五氯苯酚c，s（poly（n），1）=SZK对于c和s的这个范围，后者改进了定理2.10第1部分提供的界限结合定理3.1和2.8，我们得到：推论3.2对于每一个c，s如在Thm中。3.1，IPc，s（1）在补数下闭合。定理3.1可以推广到非常数完备性和可靠性如下。定理3.3对任意常数δ >0和任意函数对c，s使得c（n）2+δ> s（n），IPc，s（1）事 实 上，这甚至对非常数δ = π（1/log n）也成立。3.2只发送一条信息我们有时能够减少证明系统与简洁的证明，发送一个单一的消息到上述情况（证明，只发送一位）。定理3.4对于任意b=b（n）=O（logn），c=c（n），s=s（n）满足s2−b/2，1−exp−κ s2b/（1−s22b），其中reκ是一个普适常数。（条件2保证h在1SJ=exp（O（s2b/（1s22b）处至少为t1/poly（n），并且条件3保证c2>SJ。）特别地，在以下两种情况下满足上述条件1. b≤O（logn），s=O（2−b），c= 1−o（1）。2. b≤2 log2 log2n，s=（1− Ω（1））·2−b/2，且c≥1−exp（−ω（2b/2））。从PCP系统的角度来看，上述结果涉及PCP的一般化，其中允许非布尔查询。具体地，上述结果涉及PCP系统，其中进行单个查询并且由b位长的字符串回答。这种方案的分摊查询复杂度可以被视为b，因此第2项中的设置断言1-查询PCP与多-2名义随机性，常数（甚至双对数）答案大小，完美的完整性，以及摊销查询复杂度低于2的单位是SZK。这与定理2.10的第2部分稍微相关，定理2.10的第2部分提到摊销查询复杂度低于1，但在不同的PCP模型中（一方面，允许许多布尔查询和任意完整性约束，但另一方面，只对数随机性）。3.3关于发送有界位数的证明器对于更多比特的通信，我们首先获得以下具有完美完备性的交互式证明结果（用IP+表示）：定理3.6 IP+（b）复时间（2b·poly（n））.时间复杂度为O（log n）。在一般情况下（即，不完美的完整性），我们证明：定理3.7 IP（b，m）≠ coAM（2 b·poly（mm，n），O（m））. 特别是时间复杂度O（logn），时间复杂度O（logn），上述定理提供了第一个证据，证明NP完全问题不能有交互式证明系统，其中证明者发送很少的比特。通过应用定理2.3和定理2.5，可以得到进一步的证据推论3.8 IP（b，m）双链AM（poly（2 b，mm，n）m，2）. 时间复杂度为O（log n），O（1）和IP（polylog n）CycoAM。推论3.9 NP/NIPIP（O（logn），O（1））除非多项式时间层次崩溃（到NIP2=（1992）。 NP/NP/IP（polylog n），除非是1.2× 1.2 ×1.2。在上面，coAM和coM2表示coAM和coM2的准多项式时间（2polylogn）类似物。3.4关于发送有限数量消息最后，我们提到我们的消息复杂性的结果（更精确的说明见第8节。）定理3. 10Letm（n）≤n/logn是一个“nice”流函数，并假设#SAT∈/AM（2 o（n），2）. 则AM（poly（n），m（n））/= AM（poly（n），o（m（n））。注意，根据定理2.4，我们在这个定理中使用IP还是AM是无关紧要的10XXXdef2XXX4关于极其简洁的证明者（只说一点）在本节中，我们证明定理3.1。这个证明是基于下面的引理，以及以前的结果。引理4.1对于每两个常数c，s，IPc，s（1）中的每个问题都归结为SDc，s。证明：让（P，V）是某个问题的交互式证明，这样证明者在整个交互过程中发送一个因此，在输入x和内部硬币投掷r时，验证者首先发送一条消息，表示为y=Vx（r），证明者用一个比特回答，表示为σ∈ {0， 1}，验证者通过评估谓词Vx（r，σ）∈ {0， 1}来决定是接受还是拒绝。一个特殊的情况-独特的答案。 为了证明主要思想，我们首先考虑自然的情况，其中对于每个对（x，r），恰好存在一个σ使得Vx（r，σ）= 1。(Note否则，输入x和验证者的内部硬币投掷r上的交互对于这种特殊情况（我们称之为唯一答案），我们将证明以下内容：4.2如果一个问题有一个IPc，s（1）证明系统，其答案是唯一的，那么它可以简化为：SD 2c−1，2s−1。注意，只有当s≥1/2时，才能满足h的最大值h。证明：令σx（r）表示满足Vx（r，σ）= 1的唯一σ 证明者例如，如果对于某个x和随机r，σx（r）的值由Vx（r）确定，那么证明者可以说服验证者以概率1接受x（通过回复σx（r））。另一方面，如果对于某个x和随机r，σx（r）的值在统计上独立于Vx（r）（并且是无偏的），则证明者没有办法说服验证者以概率接受x高于1/2。本文提出了一种新的证明方法，其中C1（r）d=ef（Vx（r），σx（r）），C2（r）d=ef（Vx（r），σx（r）），其中b表示ab的完全性.现在，我们将C1和C2采样的分布之间的统计差异验证者的最大接受概率因为C1和C2的第一个分量是X x分布相同，它们的统计差异正好是第一个分量以Vx（r）为条件的第二分量之间的统计差异的Vx（r也就是说，（C1，C2）=E [σx|y，σx|y）]，X xy←Vx其中σx|y表示当r在{rJ：Vx（rJ）= y}中均匀分布时σ x（r）的分布。对于任意y和b∈ {0，1}，设qb|y表示σx|y=b。对于任何固定的y，（σx|y，σx|y）= |Q1|y — q 0|y| =2qy−1,whereqy=ma xb∈{0,1}{qb|y}≥ 1。因此，我们有：（C1，C2）=E[2 qy− 1]。X xy←Vx另一方面，（P，V）中的最优证明者策略是：在接收到y时，用使q b最大化的b来响应|y.当证明者遵循这个策略时，我们有Pr[V接受x]=Ey←Vx[qy]。11- -XX把后两个方程放在一起，我们得出结论：（C1，C2）=2· Pr[V接受x] −1。3因此，如果证明系统分别具有完整性和可靠性误差边界c和s，则简化将实例映射到分别具有距离边界2c 1和2s 1的对4这就确立了索赔4.2。一般情况下。现 在 我们继续讨论一般情况，其中可能存在对（x，r），使得要么两个σ都满足Vx（r，σ）=1，要么它们都不满足。我们是通过把这个一般情况归结为特殊情况来做到这一点的4.3如果一个问题在IPc，s（1）中，那么它有一个具有唯一答案的IP（1+c）/2，（1+s）/2（1）证明系统。显然，引理4.1是由权利要求4.2和4.3的组合证明：设（P，V）是一般的IPc，s证明系统.考虑以下修改的验证者策略，表示为VJ。1. 为原始验证者V生成掷硬币r。2. 根据Vx（r，σ）=1的可能证明者响应σ的数量j，进行如下操作：情况j=2：向证明者发送一个特殊的“以1响应“消息，当且仅当证明者以1响应时案例j=1：从以下其中一个窗口开始运行（每个窗口具有1/2的概率）：发送证明器y=Vx（r）并接受，当且仅当证明器以唯一的σ响应，使得Vx（r，σ）=1。向证明者发送一个特殊的“respond with 1“消息，当且仅当证明者响应1时情况j=0：选择随机位σ。向证明者发送一个特殊的对于所有可能的VJ抛硬币的选择，只有一个证明者的响应会让VJ接受。因此，VJ满足特殊情况的条件为了建立权利要求4.3，我们知道，如果一个最优证明者使V以概率δ接受，那么一个最优证明者使VJ以概率（1+δ）/2接受。要看到这一点，观察VJ的最佳证明者策略PJ包括总是对特殊消息响应可以通过检验来验证，在j的每个值的条件下，如果P使V以概率δj接受，则P J使V J以概率（1 + δj）/2接受。（也就是说，δj是V在与最佳证明者交互时接受的概率，条件是V选择随机r，对于该随机r，存在j个接受答案（即，j=|{σ：Vx（x，σ）= 1}|）. 实际上，δ0= 0，δ2= 1，且δ1≥1/2。）Q3注意，在特殊情况的假设下，对于每个x，证明者可以说服验证者接受x。其概率至少为1/ 2（因此这样的非平凡证明系统必须具有至少1/ 2的可靠性4注意，这种关系被SDα，β的自然IP（1）系统颠倒，其中验证者从两个分布之一随机选择单个样本，并要求证明者猜测哪个分布这个样本来自哪里如果分布在距离δ处，则证明器以概率1+δ成功。因此2 2将这个证明系统应用于SD2c−1，2s−1，我们分别得到了完备性和可靠性界c和s··12|| ||−| |||结合权利要求4.2和4.3，引理（即，引理4.1）如下。具体地，根据权利要求4.3，IPc，s（1）中的任何问题具有唯一答案（1比特）交互式证明，该唯一答案（1比特）交互式证明分别具有完整性和可靠性，即dscJ=（1+c）/2和dssJ=（1+s）/2。根据权利要求4.2，后者包括：系统意味着问题可简化为SD2cJ−1，2sJ−1=SDc，s（因为2cJ− 1 =（1+c）−1 =c和2sJ− 1 =（1+s）−1 =s）。定理3.1的证明：设c和s满足定理3.1中的条件。在SZK中包含IPc，s（1）是通过结合引理4.1和定理2.6得出的：也就是说，IPc，s（1）简化为SDc，s，它（对于1> c2> s > 0）存在于SZK中。相反的包容性（即，SZK在IPc，s（1）中的值）由定理2.9得出具体地说，c1且s > c/2，且设m>0使得c+m≤1且s≥（c/2）+m。 对于SZK中的任何问题，考虑一个验证器，它执行定理2.9的IP1−2−n，1/2（1）证明系统，概率c +n≤ 1，否则拒绝，没有任何交互。这就产生了一个证明系统，它具有完备性（c+n）·（1− 2−n）> c（对于足够大的n）和可靠性（c+n）·（1/2）β，并输出一对分布（XJ，YJ），使得：（X，Y）≥αX（X，Y）≤β（XJ，YJ）≤2−k在此基础上，提出子一种新的计算方法，即：a_（X，y，1/（α）），a_（X，y，1/（α）），a_（y，y，1 /（α）），a_（x，Y1/（α）），a_（y，y，1 /（α），a_（y，y），a_（y，y，y），a_（y，y，yβ），exp（1/δ），k），其中eδ定义为α2+δ= β。定理3.3的证明：设c，s与定理中相同，考虑IPc，s（1）中的任何问题。引理4.1的证明显示了如何从任何实例x，我们可以在多项式时间内构造一对分布（X，Y），其统计差异至少为c（x）（分别为，至多s（x））当x是YES实例时（分别地，没有实例）。1998年，张晓刚（|X|），β = s（|X|），且k = 2，给出了从1/4到SD3/4，1/4的减少，其在SZK中。这个红uct ion在多项式时间内是可压缩的，因为1/（α−β）=1/（c−s）≤pol y（|X|）（根据IP的定义）和exp（1/δ）≤ poly（|X|），因为δ =（1/log |X|（假设）。关于c和s的限制。定理3.1中的c2> s约束是由于定理2.6中的类似约束（其又源于引理4.4中的限制）。回想一下，对于每一个1> α > β > 0，SZK中的每一个问题都简化为SDα，β（参见。[怎么样？]）.然而，不知道对于每个1> α > β > 0（而不是定理2.6中的每个1> α2> β > 0），SDα，β是否在SZK事实上，后者是一个有趣的开放问题，我们建立了它的等价性的一个quet i上rega rdinggIPc，s（1）（对于一个r比特rary1>c>s>c/2>0）。定理4.5下列假设是等价的。1. 对于所有α，β使得1> α > β > 0，SDα，β在SZK中。2. 对于所有常数c，s使得1> c> s> c/2> 0，IPc，s（1）≠ SZK。13⊆⇒⇒联系我们4联系我们≤{}→{}回想一下，SZK IPc，s（1），对于每个c，s，使得1> c > s > c/ 2> 0。(Note这实际上是在上述定理3.1的证明中建立的，因为实际使用的条件是c1和s > c/2。）证明：方向（1）（2）以与定理3.1相同的方式被证明，除了我们现在使用假设（1）而不是定理2.6：具体地，IPc，s（1）减少到SDc，s（对于每个c，s由引理4.1），假设（1）断言后者驻留在SZK中。通过回忆SDα，β在IP（1+α）/2，（1+β）/2（1）中的情形，证明了方向（2）（1）（见[？[1]和F（注4），其中H（2）在SZK中是连续的（因为对于任意1 > α > β > 0，（1+α）/2>（1+β）/2>（1+α）/4成立）.最后，我们注意到定理3.1中的条件s > c/2（或者更一般地，对于SZK IPc，s（1））是必要的。提案4.6（参见，[？，对于每一个c，s使得s< c/2，IPc，s（1）= BPP.5关于发送一个信息在这一节中，我们证明定理3.4，它将具有简洁证明器的2消息证明系统为证明器仅发送一位的证明系统设（P，V）是一个IPc，s（b，2）证明系统，其中s2−b/2。与第4节一样，我们可以假设在输入x和内部硬币投掷r时，验证者首先发送消息y=Vx（r），证明者用字符串z0， 1b回答，验证者通过评估谓词Vx（r，z）0， 1来决定是接受还是拒绝。我们获得一个新的证明系统（PJ，VJ）通过随机构造5.1（修改的证明系统（PJ，VJ））。 在输入x上，各方的行为如下：1. VJ：均匀地选择r，令y = Vx（r）。 选择一个随机函数h：0，1 b0，1.把y和h送到PJ。2. PJ：设z = P（x，y），σ = h（z）.将σ发送给VJ。3. VJ：A∈i如果r∈ x∈w∈{0，1}b使得h（w）=σ且Vx（r，w）=1.显然，（PJ，VJ）的证明者到验证者通信是1是1位，并且验证者分析（PJ，VJ）的错误概率更为复杂。5.1接受概率-唯一答案甚至比第4节更有启发性的是，首先分析独特答案的自然特例。也就是说，我们假设对于每个对（x，r），恰好存在一个z使得Vx（r，z）= 1。权利要求5. 2若（P，V）具有唯一性，则（PJ，VJ）具有完备性SJ=（1+c）/2和可靠性SJ=（1+sj）/2. 此外，（PJ，VJ）也是唯一的.注意cJ≥c且1−sJ≥1−s另一方面，sJ

下载后可阅读完整内容，剩余1页未读，立即下载