有效论证中的PCP：哈佛公开论文分享与计算复杂性电子讨论会TR 09-089的研究成果

有效论证中的PCP是固有的哈佛社区公开了这篇文章。请分享这种访问如何使您受益。你的故事很重要引文Rothblum，Guy N.，和萨里尔·瓦丹2009年有效论证中是否固有PCP？计算复杂性电子讨论会TR 09 -089。发布版本http://eccc.hpi-web.de/report/2009/089/可引用链接http://nrs.harvard.edu/urn-3:HUL.InstRepos:4854423使用条款本文从哈佛大学的DASH存储库下载nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-2SSSSPPSP在本文中，我们考虑的问题是，PCP是否真的是非常有效的论点所必需的我们的动机之一只是为了更好地理解复杂性理论和密码学中这两个基本概念之间的关系此外，在有效的参数系统中使用PCP的缺点是，协议及其应用程序继承了PCP定理的复杂构造和证明虽然在简化PCP定理[BS，Din]方面已经有了一些实质性的进展，但它仍然非常重要，并且该构造可能仍然过于复杂而无法在实践中使用。我们在这里研究的问题以前已经被Ishai，Kushilevitz和Ostro-vsky [IKO]考虑过他们表明，通过使用更强的加密原语，即（加性）同态加密而不是抗碰撞哈希，可以使用更简单的指数长度的“Hadamard PCP”[ALM + ]而不是完整PCP定理的多项式长度的PCP来构造一些有效的参数他们的论点只是多对数）通信，但是验证者到证明者通信是多项式的（参见[GVW]）。我们的成果。 在本文中，我们提供的结果表明，PCP是必要的构造，ING有效的论点。具体地说，我们考虑了一个基于广泛的密码原语（例如，抗冲突散列、RSA假设、同态加密），其中计算可靠性基于通过有效归约的原语安全性。也就是说，存在一种算法，使得如果证明者策略是说服验证者接受错误陈述的任何证明者策略，则P“打破”密码学[2]实际上，我们提供了一个密码原语的一般公式，以及“打破”这样一个原语意味着什么这个公式是相当普遍的，涵盖了标准的原语，如单向函数或同态加密，以及特定的假设，如分解的难度。对于这样的构造，我们展示了如何构造PCP，其效率与参数系统、缩减以及用于“实现”密码原语的各种方法有关（下面将非正式地，我们的建筑工程如下。我们将PCP预言视为为论证系统指定证明者策略PPCP（即，下一个消息功能）。PCP验证人：1. 解析密码原语的2. 用PPCP实现了变元系统的验证器，3. 用PPCP代替还原S，和4. 如果参数系统的验证者都接受（在步骤2中）并且没有破坏加密原语（在步骤3中），则接受为了建立可靠性，我们注意到，如果PCP使参数系统的验证者相信一个错误的陈述，那么将破坏密码原语;这意味着至少有一个接受条件将失败。因此，PCP的可靠性在理论上无条件地保持信息，而不管上面步骤1中选择的实现方式如何。 为了完整性，我们需要确保步骤1中选择的（加密原语的）实现不能被P破坏，其中P是诚实的证明者。我们提供了几种方法来实现这一点，一些基于复杂性假设和一些无条件的。 下面我们将介绍其中的一些以及由此产生的PCP参数。[2]因此，我们要求归约在其对P的访问中是3∈SSLS| |SP实现和参数。参数和PCP有许多参数，我们尽可能多地 但为了简单起见，在当前的讨论中，我们将重点放在几个感兴趣的参数和典型设置上。（特别是，我们忽略证明者和验证者的计算时间。 考虑一个由加密原语C为语言L NP构造的参数系统，使得在长度为n的输入上，该参数系统具有证明者到验证者的通信复杂度polylog（n）和完整性和可靠性误差1/3。而且这是一个p（n）-时间约化S，使得对于每个x∈/L，每个加热过程都在P上，如果P说服验证者以至少1/ 3的概率接受，则P（C，x）对我们来说，三个关键参数是验证者到证明者的通信复杂度v=v（n）;轮数r=r（n）;以及对其oracle的查询次数q=q（n）。KilianThe Ishai et al.从同态加密的[IKO]构造具有v= poly（n）和r，q=O（1）。鉴于上述情况，我们得到的PCP将始终具有恒定的完整性和可靠性误差以及字母大小polylog（n）。我们的PCP的查询复杂度将是r+q，与PCP中参数的已知结构相我们的PCP的长度是2|C|+v，其中C是由验证器生成的密码原语的实现的描述长度。注意，如果C=O（v），则这匹配来自PCP的参数的已知构造，例如，指数长度的PCP对应于v= poly（n），并且多项式长度的PCP对应于v=O（logn）。在本文中，我们提出了几种方法来实现所使用的构造的密码原语。回想一下，我们的PCP验证器需要生成不能被P破解的密码原语的实现C，其中是参数系统的诚实证明者这是通过各种不同的方式完成的，我们在下面概述了一些：上面的一般框架在第4节中进行了形式化，在那里我们还提供了一个自然（和有效）的实例化。 假设我们有一个通常意义上的加密原语的安全实现，例如。 存在抗冲突的散列函数或者存在同态加密方案，其具有由底层变元系统使用的任何安全参数（通常为polylog（n）以实现多对数通信）以及对抗多（n）时间对手的安全性。这样的原语不能被P破缺，因为这是一个poly（n）时间算法。然后，由于实现C是由固定算法描述的（其获得安全参数作为输入），因此它可以硬连线到PCP协议中在这里，我们得到了一个标准的（信息理论上健全）PCP，其中的完整性依赖于假设原语的实现是安全的。 我们认为我们在这里使用的假设是很自然的，因为如果没有原语的安全实现，那么最初的构造是一个明显不那么有趣的对象。在第5节中，我们考虑了更严格的归约概念，其中参数系统中的所有实体仅被给予对诸如单向函数、伪随机函数族或抗冲突哈希族之类的密码原语的黑盒访问我们表明，在某些情况下，我们可以最小化或完全删除上述结果中的计算假设（对于这种完全黑盒约简）。要做到这一点，我们注意到，我们使用的加密原语的实现只需要针对··4S| |S| |S||SPP∈{}{}∈{}P：单一固定多项式时间算法。 获得一个对固定多项式时间有界算法安全的实现可能比获得一个对任何多项式时间算法安全的实现（密码原语的通常要求）要容易得多。例如，我们实际上可以使用[IW]构造种子长度为C = O（log n）的伪随机函数C，在最坏情况复杂度假设E =DTIME（2 O（n））没有大小为2 o（n）的电路的情况下。我们还可以使用一系列poly（n）独立的哈希函数来获得针对P的抗碰撞哈希函数的无条件实现，从而产生C=poly（n）。或者，从这样的一个族中随机选取poly（n）散列函数并将它们硬连接到PCP验证器和证明器中，我们可以得到C=O（logn）的非均匀PCP构造（这也可以看作是一个统一的结构，在共同参考字符串模型。）3我们强调，即使我们在一些转换中使用复杂性假设，所得到的PCP也达到了标准的可靠性统计定义-不存在任何可以说服验证者接受错误陈述的证明预言，除非概率很小。事实上，复杂性假设只用于我们构造的（一些）完整性，以确保描述证明者的诚实证明神谕不会无意中允许（归约）破坏原始。这种条件完备性不同于原始论证系统的可靠性，原始论证系统也是在相同的假设下成立的，但只能保证不受有界恶意证明者的影响。Perspective.像所有关于约简的否定结果一样，我们的结果并不完全排除“没有PCP”获得有效论证的可能性，也可以解释为建议这样做的途径。一种可能性是在从破坏密码原语到破坏可靠性的简化中使用非黑盒的作弊证明策略（或者至少使用这样的事实，即验证是有效的）。另一个是利用减少，使许多查询q的作弊证明，即使当健全性是违反恒定的概率。（如果q= poly（n），我们得到一个带有poly（n）查询的PCP，这是平凡的。另一个方向是使用一个还原，其中破坏可靠性的恶意证明者甚至说常数概率只破坏了使用多项式小的优势的密码原语。这样的减少也将只产生具有多项式查询复杂度的PCP已知的减少是不是上述任何一种类型。2分类和定义设[n]为集合1，2，. . . n.对于x，y0， 1n，我们使用x y表示x和y的连接（0， 12n中的字符串）。对于集合X上的（离散）分布D，我们用x D表示通过分布D选择x X的实验。一个函数f（n）是可忽略的，如果它小于任何（逆）多项式。 我们建议读者参考[Gol1，Gol2]，以获得本工作中使用的标准加密对象的完整定义，例如单向函数，分布集合，抗冲突哈希函数和伪随机函数。我们强调，在整个工作中，每当我们做出或提到硬度假设时，这些假设总是针对非均匀的对手。我们目前的两种类型的证明系统，我们认为在这项工作的定义3使用PCP和近似硬度之间的联系，该构造也可以被视为从L到MAXSAT的近似版本的随机约简（参见，[BGS]）。5PPV∈{} L VV P P VVL∈ NT IMEP•∈LLP V定义2.1（参数系统（，）[BCC，GMR]）。一个语言（g（n））的论元系统由两个交互式机器组成。（x，w）得到一个输入x和建议01-02|X|）（通常是输入成员的NP见证）。 （x）得到输入x。这些要求是：C（n）的完全性。对于每一个x和x在中的成员资格的相应见证人w，• Soundnesss（n）vs. sizef（n）. F或每一个x∈/L，每一个（非均匀）大小的加热P∈f（n），（P∈（x），V（x））使V接受的概率至多为s（n）。有许多我们感兴趣的论证系统的复杂性度量，例如通信复杂性（在每个方向上），轮复杂性，诚实证明者和验证者的大小等等。定义2.2（PCP，概率可检验的证据（P，V））。语言L∈NTIME（g（n））的一个论元系统由一个非自适应的（即. 无状态）机器P和Oracle机器V。 1、求出一个函数x，x ∈ { 0，1 }，x ∈ { 0，1}|X|）（通常是输入在L中的成员关系的NP证明）和输入Oracle查询。V（x）得到输入x。这些要求是：• C（n）的完全性对于每个x∈ L和x在L中的成员资格的相应证明w• Soundnesss（n）. 对于每个x∈/L和每个非自适应加热P_∞预言，V（x）P_∞（x）接受的概率至多为s（n）.PCP系统的复杂性度量方法有很多，已经得到了广泛的研究。 在这项工作中，我们专注于查询的复杂性（甲骨文调用的数量），字母表的大小（输出的大小） ， PC P 长 度 （ 可 能 的 输 入 查 询的 数 量 ） ， 诚 实 的 证 明 者 和 验 证 者 的 大 小 ， 等 等 。3密码原语和约简在本节中，我们考虑从密码原语到计算上可靠的参数系统的约简我们想考虑密码原语和归约的一般概念我们在这里提出的概念已经包含了大量的密码学原语，如单向函数、加密方案、特定假设等等。请参阅下面关于它们如何符合形式主义的讨论。定义3.1（密码原语）。密码原语（C，T）由电路类C和测试过程T定义。对于C中的候选C（类中的电路），我们说交互对手A（κ，ε）-破坏C，如果：PRTT A（C，1 κ，1 [1/ε|）接受≥ 2/3另一方面，我们说C对A是（κ，ε）-安全的，如果：PRTT A（C，1 κ，1 [1/ε|）接受≤ 1/36一T·A Aa不{}→{}不一{}A TC{}{}→{}κAA{}A不联系我们C其中在两种情况下都被给予对电路C的访问。在整个工作中，我们只处理C，并且对于C有一个promise，要么破坏C，要么C是安全的。输入参数κ通常用于表示限制电路C的输入和输出大小的安全参数（不满足此界限的4直观地说，参数ε用于指定破坏原语的成功概率的请注意，上述概念可以扩展到考虑电路分布的类别（而不是电路，或支持大小为1的电路分布，如上所述）。 为了简单和清晰，我们使用更严格的概念（定义3.1足以涵盖我们在这项工作中考虑的所有密码原语）。我们继续考虑几个例子，以及它们如何符合上述加密原语的定义：1. 单向函数这是计算一个函数的电路类，比如从0，1κ到0，1κ。给定电路C和对手，测试器A（C，1 κ，1 [1/ε|）选择O（1/ε）个随机输入到函数中，将C应用于每个输入，并在每个输出上运行。如果对手在这些输出中的至少一个上反转C（即，对于输入x之一，C（A（C（x）=C（x）），则接受。如果f：0， 1<$0， 1<$是一个（长度保持的）单向函数，这意味着它在多项式时间内（在其输入长度上）是可计算的，并且对于任何PPTA和p多项式p（·），对于任意大的eκ，fκ是s（κ，1/p（κ））-安全的针对Aκ。 也就是说，本文证明了：Pr[TAκ（fκ，1κ， 1p（κ））accepts ]≤ 1/ 3，其中fκ和Aκ是f和A对长度为κ的输入的限制。我们也可以考虑次指数硬单向函数。 如果f：0， 1<$0，1<$是（长度保持）次指数难单向函数，则它在多项式时间内（在其输入长度上）是可计算的，并且对于某个常数δ>0和每个概率算法A在时间上至多运行2κδ，对于足够大的κ，f是（κ，1/ 2κδ）-安全的，Aκ。2. 抗碰撞哈希族。 这是一类电路，它评估从0，1 2κ到0，1 κ的收缩散列函数族。 也就是说，Cin得到一个种子s和一个输入x作为输入，并输出函数Cs（x）=C（s，x）。测 试 者选择O（1/ε）个随机种子s1，s2，. . . s O（1/ε），并要求在每个上找到冲突，如果在至少一个上成功，则接受（即，如果给定任何种子si，对手（si）找到x且xJ使得C（si，x）=C（si，xJ））。3. 保理的难度 我们还可以将特定的数论（或其他）假设视为我们框架中的加密原语。例如，为了捕捉因式分解是困难的假设，我们对每个安全参数值都有一个单独的电路C κ。这个电路Cκ是挑选两个随机κ/2位素数并输出它们的乘积的规范电路测 试 者T取O（1/ε）个随机样本（数）{n1，n2，. . . ，n O（1/ε）}的分布。然后，它要求A对这些数字中的每一个进行因式分解，如果A在至少一个上成功，则接受A（A找到将ni分解为两个素因子的非平凡因式分解4. 同态加密方案。同态加密方案是一种具有特殊同态求值过程的（公钥或私钥）方案，该同态求值过程可用于密文序列以计算明文的某个函数f的加密（常见函数包括加法和乘法）。该方案在语义上仍然是安全的，[4]请注意，κ也可以用来限制电路C的大小，我们在本工作中不会这样做7∈CC··→→C TLR PVS CT被给予计算这种同态评估过程的电路的对手。有关语义安全加密方案的更多详细信息，请参见[Gol2]。在本例中，是执行密钥生成、加密、解密和同态求值过程的一类电路测试者使用C生成一个密钥，并将此密钥和同态评估过程（对于公钥方案，对手也被赋予加密过程）提供给然后测试者和攻击者运行语义安全博弈O（1/ε2）次，如果攻击者在这些实验中在破坏方案的语义安全性方面具有优势ε，则测试者接受讨论请 注意，密码原语的定义与是否存在原语的实现的问题是分离的，该原语的实现对于一组对手是（κ，ε）安全的。 Naor [Nao]的相关工作也考虑了密码学假设和原语的一般概念。 这项工作提出了可证伪假设的概念：存在一个程序来测试给定对手是否打破假设的假设。这里的主要焦点是根据密码学假设被证伪的效率对它们进行分类。 在这种情况下，目标之一是设计特定的程序，不仅打破密码学假设（假设它可以被打破），而且以一种可以非常有效地验证的方式这样做。 在我们的加密原语的概念中，我们考虑可证伪的原语，但我们专注于验证任意对手（由安全性降低提供）破坏加密原语。可证伪的（甚至只是有点可证伪，参见。[Nao]假设）自然落入我们的加密原语框架中。不可证伪的假设，例如指数假设[Dam]的知识，可能不适合我们的概念。 这是因为没有“测试程序”可以用来判断对手是否打破了假设。既然我们已经提出了密码原语的概念，我们继续定义一个从加密原语到计算上可靠的参数系统的简化定义3.2（减少）。从由（，）定义的密码原语到语言的自变量系统的约简=（，，，（，），κ（），ε（））由几个分量组成。我们用x表示一个n位的输入，它的成员资格正在被证明，w表示证明者的辅助输入（通常是NP证明）。1. 如定义3.1中的密码原语（C，T）2. 两个函数κ：N N，ε：N[0， 1]，其将密码原语的参数确定为输入长度的函数函数κ（）确定安全参数，ε（）确定破坏参数的可靠性的对手在破坏密码原语方面的优势53. 两台交互式预言机：证明者P（C，x，w）和验证者V（C，x），可以访问C中的候选电路C。4. 一个安全性证明：一个预言机S，它可以黑盒访问一个作弊证明器P（C，x），该证明器在C中得到输入C，x∈ {0， 1}n。我们要求t（P（C，·，·），V（C，·））对于每个候选项C∈C都是完备的. 对于安全性，我们要求：如果一个P_∞（C，x）上的加热过程对某个x∈L和C违反S可靠性，则n个SP_∞（·，x）5我们发现用约简来确定安全参数κ=κ（n）和破解密码原语ε=ε（n）的优点是方便的，而不是把κ作为所有算法的输入。8不SC打破了（假定为硬）C。如果C确实很难被打破，那么论证系统就是合理的。我们在下面正式说明这些要求：1. C（n）的完全性对于C中的每一个C，给定x∈ L和一个有效的证明w，证明者P（C，x，w）以至少c（n）的概率使V（C，x2. soundnesss（n）的安全性。对于每个CinC，每个n位输入x∈/L和每个欺骗证明者P<$（C，x）：如果（P<$（C），V（C））（x）以概率至少接受s（n），则SP（·，x）break s C，即：P r TSP（·，x）（C，1κ（n），1[1/ε（n））|）接受≥2/3为了简单起见，我们可以认为ε（n）=s（n）O（1）贯穿整个工作。我们始终假设s（n）≤ 0。1且c（n）≥ 0。9. 我们使用t（n）来表示电路大小SP（即，t（n）是|S|·|P|，这里我们仅指诚实的P），q（n）表示由T S P进行的P-oracle查询的数量。[6]我们用v（n）表示从V发送到P的比特数的界限，用u（n）表示P的每个答案的长度（以比特为单位）的界限在定义3. 2的归约概念中，论证系统中的所有算法（证明者、验证者、测试者）都可以访问C定义中唯一的“黑盒”访问是安全证明对欺骗证明器的访问。这是一个相当普遍的还原概念。参见Reingold、Trevisan和Vadhan [RTV]对不同归约概念的讨论在这项工作中，我们也考虑更多的限制概念。（完全）黑盒约简是算法将C作为黑盒访问的约简。我们还将考虑具有有界自适应性的黑盒约简。 参见第5节，了解这些更受限制的约简类型的讨论和定义。参见附录A，了解已知论元结构的概述以及它们如何融入我们的框架的讨论。4从论点到PCP在这一节中，我们从（C，T）指定的密码素到语言L的一个论元系统进行了一个约简R=（P，V，S，（C，T），κ（·），ε（·）），并由此构造了L的一个PCP.4.1泛型转换对于我们所有的结果，我们需要一个额外的属性从减少。我们要求有可能为密码原语生成候选者Cin，当它与诚实证明者一起运行时，不能被安全证明P破坏我们在下面形式化这个属性。财产4.1. 约简R（具有可靠性s（n））有一个（多项式时间确定性）生成过程G（1 n），它在C中输出一个候选者C，使得对于每个x∈ L和每个有效的子空间sw，对于x在L中的最优解，C是s（κ（n），ε（n））-s对S P（·，x，w）（·，x）的解. 7[6]自始至终，每当我们提到依赖于P的参数的界时，我们指的是输入的最坏情况界，作弊证明者，等等。对于输入长度n。注意，这些界限还可以取决于安全参数κ（n），其是约简的参数。[7]回想一下定义3中的内容。1通过假设测试过程接受A，我们可以捕获“针对A的安全性概率最多为1/39GGGSV∈LRRGC TLR PVS CT验证人VPCP（C，x）1.选择随机硬币为V。在交互式论证系统中模拟V（C，x），这些硬币和候选者C，使用PCP证明器PPCP来获得这些硬币和候选者C的消息。因此，对PPCP的每个查询指定交互式参数的转录本（验证者论证系统拒绝，然后拒绝。否则，继续执行步骤2。2. 重复下面的O（log（1/α））次，其中α=α（n）是一个参数：使用现有的抄本和所选择的随机硬币来计算消息如果V用独立的随机硬币运行测试器TSPP CP（C，1n， 1）1/ε（n）¶），以检查是否对PPCP的每个查询指定交互式变元的转录如果在至少一半的这些迭代中T接受，则拒绝。否则接受。SPP CP 布雷克角在这里，PPCP扮演回答S再说一遍，（Honest）PCP Proof OraclePPCP（C，x，w）对于任何为交互式参数指定过去消息的文本的查询，P（C，x，w）并输出下一条消息。在第5节中，我们将这个概念扩展到概率生成器。在本节中，我们将把注意力限制我们现在为属性4.1的约化指定一个 我们稍后将展示如何通过构造满足属性4.1（无条件或在各种假设下）的生成器来实例化特定密码原语的通用构造。 我们将PCP的验证器视为Oracle机器（具有对证明或Oracle证明器的Oracle访问）。我们运行生成器G来生成候选者C。通用验证者VPCP和（诚实）证明者oraclePPCP依赖于该候选者C。图1：验证器VPCP图2：（诚实）PCP证明OraclePPCP假设x∈/L加热PCP提供PP PC P使验证器VPCP如果在步骤1中以概率s（n）或更大的概率接受，则约简保证在步骤2中，PPCP将用advan标记eε（n）正确地破坏kC（并且PCP拒绝）。这保证安全。另一方面，当x时，我们通过性质4.1知道C是（κ（n），ε（n））-安全的，不受诚实证明者运行的安全性证明的影响（因此验证者通常应该接受）。这保证了完整性。我们在下面的定理中将其定理4.2. 令=（，（，），κ（），ε（））是从（，）指定的密码原语到定义3.2中的语言的参数系统的约简。进一步假设它满足性质4.1，并且有一个硬候选的生成器设c = c（n）和s = s（n）是论证系统的完备性和可靠性，取ε = ε（n）和κ = κ（n）。回想一下，v = v（n）限制了从V到P的通信，u = u（n）限制了P的答案长度，值r = r（n）限制了轮数，q = q（n）限制了T S P（C，1 n，1 [ 1 /ε]）进行的P-查询的数量|）的。则（PPCP，VPCP）是L的PCP，具有完备性c−α和可靠性max {s，α}。的查询次数为r + O [log（1/α）·q]。字母表的大小为2 U。PCP的长度为2 V。10V•VVTS·RSTP V--VV•PPPVP此外，PCP预言机可以在P（C，x，w）的时间多项式中构造。PCP验证器的运行时间是G、V（C，x）和T SP（C，1 n，1 [1/ε]）的多项式|）的。证据 我们首先分析所提出的构造的字母表大小、长度和查询编号：• 查询数量：验证者VPCP在步骤1中向P PCP进行r次查询（V和P之间的每一轮通信一次）。然后它运行S的O（log（1/α））模拟，每个模拟进行q次查询。因此，查询的总数是r+O[（log（1/α））·q]。字母大小：PCP的答案是证明者在交互式论证中发送的消息，它们的长度以u为界，字母大小以2u为界。PCP长度：PCP进行的每个查询都包括交互式参数的转录。因此，每个这样的查询的长度是v，并且PCP的长度是2v。我们现在把我们的注意力转向完整性和可靠性。对于可靠性，假设x∈/L，但P∈CP是验证者P CP在Step1中接受，概率至少为ts。我们生活在PCP作为交互式论证的作弊证明者P根据约化的性质，我们知道P∈（，x）在破环C时具有优势ε.这意味着在步骤2中，每次PCP模拟，它接受的概率至少为2/ 3。因此（重复Θ（log（1/α））次），验证者PCP将在步骤2中以除了α之外的所有概率拒绝。如果“接受”的概率不拒绝）大于s，则验证者在步骤2中以至多α的概率接受。因此，接受的总概率至多为maxs，α。为了完备性，在PCP运算的第1根据性质4.1，候选C是（κ，ε）-安全的。因此，在步骤2的每次迭代中，将以至少2/3的概率拒绝。重复执行n（log（1/α））次，验证者在步骤2中拒绝的概率最多为α。取一个并界，当x∈L且证明者诚实时，接受的总概率至少为c−α。4.2密码学假设作为定理4.2的一个直接推论，我们从变元系统得到了PCP的条件构造如果确实存在一个计算上难以实现的候选者作为参数的构造所基于的密码4.1. 我们认为这是一个自然的假设：大概我们认为构造一个参数是有意义的，因为我们相信密码原语有一个安全的实现。给定这样的实现，我们可以“免费”得到一个PCP（具有统计可靠性）我们可以利用候选人来构建PCP。我们强调，所获得的PCP的可靠性是无条件的和信息论的，它是唯一的完整性，是基于密码学的假设。事实上，实现对固定的多项式时间有界诚实证明器是安全的（还原运行）就足够了，所以我们甚至可以使用仅对这个固定算法安全的加密原语（我们在后续部分中详细阐述并构建）。这里，从参数到密码原语的简化的概念是定义3.2的一般概念，即该减少仅在对手中是黑盒的特别地，我们得到以下（非正式）推论：11LR··不PTPPSR PVS CTR PVS CT推论4.3（非正式）。设是从密码原语到语言的计算上可靠的论证系统的一个简化。如果存在密码原语的安全实现，则可以使用变元系统来构造PCP，如定理4.2所示特别是，如果存在一个抗碰撞散列函数族，那么从CRHF到计算上合理的参数系统的任何简化都可以用于构造PCP。如果存在加法同态加密方案，则从加法同态加密到计算上可靠的自变量系统的任何约简都可以用于构造PCP。从已知的结构来看。我们首先使用NP参数[Kil，Mic，BG]的抗冲突哈希来检查已知的约简。取κ作为安全参数，从V到P的通信是v（n）=O（logn+κ）（指定散列和O（1）PCP查询），证明器回答的长度是u（n）=O（logn·κ），并且轮数是r（n）=O（1）。的Q（n）=O（1）（n = 1）（n = 1）原始的 定理4.2给出了（对于任何实例）一个PCP，它具有常数的完备性和可靠性，O（1）的查询，alpha b et大小为2O（logn·κ），并且pro为n thpol y（n）2κ。因此，如果我们采取一个多对数安全参数，PCP长度是准多项式。这与Kilian [Kil]构造（需要多项式长度的PCP）不太匹配，但正如我们在第5中所展示的，我们实际上可以（在复杂性假设下）得到CRHF的实现，满足上面的构造和对数κ。这从具有[Kil]参数的任何（黑盒）构造产生多项式长度如果我们检查[IKO]的约简，则从验证者到证明者的通信是κ乘以所使用的PCP长度的对数，v（n）= poly（n）κ（在他们的情况下，所使用的PCP是指数的，因此v（n）是多项式）。从证明者到验证者为u（n）=O（k），轮数为r（n）=O（1）。同样，调用次数SP使其达到最小化的条件是q（n）=O（1）（对于恒定的可靠性和破解加密的优势定理4.2给出了（对于任何实例）一个PCP，它具有常数的完备性和可靠性，O（1）的查询，alpha bet大小为2O（κ），并且pro=h2poly（n）·κ（因为y以指数长度PCP开始，所以应该是expected的5削弱或消除计算假设在本节中，我们考虑比4.2节中的那些更受限制的约化，并获得具有更好参数的PCP构造主要思想将是为归约所使用的密码原语构建一个实现，该实现仅针对一个特定的对手是安全的：与诚实的论证证明器一起运行归约的对手（这样的实现仍然足以通过定理4.2论证完整性在本节中，我们将研究（完全）黑盒约简和（甚至更受限制的）具有有界自适应性的黑盒约简。我们首先正式介绍这些限制性更强的约简概念定义5.1（黑盒减少。）. 一个约简=（，（，），κ（），ε（））是一个（完全）黑盒约简，如果它是一个约简，如定义3.2，并且也只有黑盒访问C，即。他们把C当作一个预言机 这里t（n）也限制了SP进行的oracle调用的数量（因为t（n）是这个过程的总组合大小）。定义5.2（具有a（n）适应性的黑箱约简）. A减少=（，，，（，），κ（），ε（））是具有自适应性a（n）的黑盒约简，如果它是定义5.1中的黑盒约简，并且具有以下结构：对于C中的每个候选者C，以及输入见证对（x，w），当12GGB.G.PV·≤RGC TLR PVS CTS P（C，x，w）运行（使用诚实证明器），对C的每个oracle调用与适应性水平i ∈ {0，. . . ，a（n）}。SP（C，x，w）所做的每个查询实际上是（i，y）形式的（其中i是自适应水平，y是实际查询）。8对于每一个i ∈ {0，. . . ，a（n）}，以及所有的形式为（k +1，y）的预言机查询，S P（C，x，w）使得y仅是形式为（i，YJ）的预言机查询的答案的函数，其中i ≤ k。我们强调，只有当S与诚实的P一起运行时，这才是必需的。在考虑有界自适应约简时要记住的一个很好的例子是使用抗冲突哈希构建的哈希树，比如将其输入缩小2倍的哈希函数。这里，一个长串被分成块，每对块被散列，散列被分成对，每对本身被散列，然后每对散列的散列被散列等等，直到获得单个“散列根”为止哈希级别的数量与块的数量成对数关系。 这种哈希树构造是[Kil，Mic，BG]的论元系统的主要组成部分，并且这些论元系统中的构造和安全性约简都具有定义5.2意义上的对数自适应性（参见附录A，以了解这些构造的进一步讨论）。可能候选人生成器。为了得到无条件结果和在较弱（最坏情况）假设下的结果，我们需要推广性质4.1。 我们需要将该属性扩展到这样的情况，即我们没有输出单个硬实现的确定性生成器，而是概率生成器输出硬实现（对于特定算法）w.h.p.。财产5.3. 约简R（具有可靠性s（n））具有概率多项式时间生成过程G（1n），其输出C中的候选者C，使得对于每个x∈ {0， 1}n和给予证明者P的建议串w∈ { 0， 1}poly（n）：PRC型糖尿病（1例）≥1−γ其中γ= γ（n）是一个参数。 我们说输出长度b= b（n），如果（1 n）始终输出一个电路C“，其描述”的大小最多为b（n）。9请注意，现在，当我们想要使用定理4.2的通用变换来进行具有属性5.3的概率生成器的约简时，我们需要PCP证明依赖于硬候选者C。为了做到这一点，我们修改（PCP，PCP），以便在步骤1中，PCP验证者将选择一个随机C（1n）。由于该候选C不是预先固定的，因此它将被包括在验证者进行的每个PCP查询中（回想C这使PCP长度增加了2b（n）倍。我们将其形式化为定理5.4的推广定理5.4. 令=（，（，），κ（），ε（））是从（，）指定的密码原语到定义3.2中的语言的参数系统的约简。进一步假设它满足性质5.3，并且有一个硬候选的概率生成器，其输出长度由b（n）限制，参数γ（）使得对于所有n，γ（n）为1/4。设c = c（n）和s = s（n）是论证系统的完备性和可靠性，取ε = ε（n），κ = κ（n），b= b（n），γ = γ（n）。 回想一下，v = v（n）限制了从V到P的通信，值u = u（n）限制了P的答案长度，值r = r（n）限制了q = q（n）限定了T SP（C，1 n，1 [1/ε]）所作的P-查询的数目|）的。8更一般地，能够从任何查询中有效地提取自适应性级别就足够了9更正式地说，存在多时间评估过程，其将电路C的b（n）位描述作为输入（例如， 所有C的单独门和线的列表）和n位输入x，输出s C（x）。13V不不SP V--VVVGS·VRVPS则（PPCP，VPCP）是L的PCP，具有完备性c−α−γ和可靠性max {s，α}。查询次数为r+ O [log（1/α）·q]。字母表的大小为2 U。PCP的长度为2 v+b。此外，PCP预言机可以在P（C，x，w）和G（1 n）的时间多项式中构造。PCP 验证器的运行时间是G（1n）、V（C，x）和TSPs（C，1 n，1 [1/ε]）的多项式|）的。证据 查询数和字母表大小的分析如定理4.2的证明中所述。PCP长度更大：由PCP进行的每个查询包括步骤1中生成的候选C（1n）（b位），以及交互式参数的转录因此，每个这样的查询的长度是v+b，PCP的长度是2v+b。在可靠性条件下，由G生成的候选者C的验证码s，假设tx∈/L，但PP∈CP使验证码PCP在Step1中以至少ts的概率被接受。我们生活在P<$CP作为C加热的证明者P<$C进行交互式论证。 根据约简的性质我们知道，P∈（，x）在破环C时具有优势ε。这意味着在步骤2中，每次PCP模拟，它接受的概率至少为2/ 3。因此（重复Θ（log（1/α））次），验证者PCP将在步骤2中以除了α之外的所有概率拒绝。如果步骤1中“接受”（即不拒绝）的概率因此，接受的总概率至多为maxs，α。为了完备性，在PCP运算的第1根据性质5.3，候选C在除了γ概率之外的所有概率下都是（κ，ε）-安全的在这种情况下，在步骤2的每次迭代中，将以至少2/3的概率拒绝重复O（log（1/α））次，验证者在步骤2中拒绝的概率至多为α。取一个并界，当x∈L且证明者诚实时，接受的总概率至少为c−α−γ。Bounded-Adjacent PRF族和CRHF族。在第4.2节中，我们基于密码学假设获得了PCP。然而，如前所述，我们需要的硬度类型比密码设置中通常的要宽松得多：我们只需要特定算法P的硬度。在这种情况下，对于将C作为黑盒访问的算法，我们甚至可以获得无条件的结果。例如，对于一个只进行q个Oracle查询的算法，q- wise独立散列函数 我们可以利用这种直觉，无条件地或在相对温和的复杂性假设下，将来自抗碰撞哈希族（CRHF）或单向函数的参数的（黑盒）构造转换为PCP。除了4.2节的（条件）结果之外，我们付出的代价是散列函数描述，以及PCP长度和验证器运行时间可能会变得很大。我们定义有界对手伪随机函数。这些函数族（从黑盒访问）看起来对有界对手是随机然后，我们将表明，有界对手PRF族（i）足以构建实例化定理5.4的通用构造的候选生成器，并且从单向函数、伪随机函数族和抗冲突散列族到自变量的黑盒归约构建PCP（ii）可以无条件地或在弱最坏情况复杂度假设下（具有各种种子长度）构建。我们还将定义有界对手的抗碰撞哈希家族（一个较弱的原语），表明它们可以用来构建一个PCP从任何黑盒减少CRHF家庭的参数系统，并提出有效的建设。我们将在5.1节继续讨论有界敌手密码原语的定义和构造。在第5.2节中，我们展示了如何使用有界对手原语来跨14一F····联系我们F形成PCP的减少。5.1Bounded-Adjuvant PRF和CRHF我们首先定义和构造有界对手伪随机函数族（PRFs）和抗碰撞哈希族（CRHFs）。 这些是函数的集合，对于有界的对手来说，它们看起来是随机的或（分别）抗冲突的。 我们不限制计算函数所需的时间：它可能比对手的运行时间更长。 我们无条件地构造这样的函数，并且在温和的复杂性假设下（以减少函数的描述大小）。定义5.5（伪随机函数）。 考虑系综F ={fn：{0，1}j（n）×{0，1}k（n）→{0， 1}l（n）}n，具有种子长度j（n）、输入长度k（n）和输出长度l（n）。我们说F是一个（s（·），ε（·））-伪随机函数（PRF）族，如果对每个（非均匀）大小s（n）和一个预言电路系综A，对除n以外的所有n.PR[Afn（seed，·）（1n）=1]−Pr[Ar（1 n）= 1]。≤ε（n）. {0，1}j（n）随机函数r：{0，1}k（n）→ {0，1}l（n）。即没有大小为s的对手可以区分族中的随机函数与真正的随机函数（除了具有优势ε）。有时候，构造看起来不是伪随机的函数族更容易，但它们是抗碰撞的。特别是，这将是有界适应性的对手的情况定义5.6（抗碰撞功能）。考虑一个可有效构造的系综= fn：0，1 j（n）0，1 k（n） 0，l（n）n，其中种子长度为j（n），输入长度为k（n），输出长度为l（n），其中k（n）> l（n）。我们说这是一个（s（），a（），ε（））-抗碰撞函数（CRHF）族，如果没有（非均匀