阅读如果知识抽取器存在,为什么Zk-咆哮是知识的争论?,我对OP的第一条声明感到困惑:
据我所知,证明知识抽取器的存在意味着完美的稳健性。
答案的重点不一定是完美无缺,但它似乎含蓄地证实了健全的含义由提取器。
首先,让我声明,当我读到“稳健性”时,我认为I的属性表明,任何Prover策略都不能使验证者相信一个符号不属于该语言,概率极小.这似乎是一个完全不同的“对象”,而不是一个提取器“溢出”的证人,所以我很难得到一个至少天真的想法,这个假设的含义。
然而,我开始相信这一点,因为我发现了一些来源,例如:
...稳健性被知识提取属性...所取代。
说到证明知识的正确性,我们有一个非常好的正式方法。与前面讨论的模拟器一样,我们需要证明一种特殊算法的存在。这种算法被称为知识抽取器,它所做的正是它所宣称的。知识抽取器(简称“extractor”)是一种特殊类型的验证器,它与Prover交互,并且--如果Prover成功地完成了证明-- Extractor应该能够提取Prover的原始秘密。这回答了我们上面的问题。为了证明知识的证明是正确的,我们必须证明每一个可能的引流器都有一个抽油器。
然而,在第4.5段中,“健全如何?”关于关于Bellare和Goldreich处理他们对PoK的表述的知识证明(https://www.wisdom.weizmann.ac.il/~oded/PS/pok.ps)的定义,我发现了以下几个词:
我们注意到,我们的定义不要求使用x,而不是在L_R中。特别是,不需要可靠性(即对验证器引导验证者接受x而不是L_R的能力的约束)。因此,用于R的知识验证器不一定定义L_R成员资格的交互式证明。这与以前的定义形成了对比;它们的“有效性”条件意味着健全性条件,因此后者总是适用的。我们认为,我们的健全性与有效性的“脱钩”在概念上和某些应用上都是合理的。
顺便说一句,这与著名的Golderich的“密码基础”4.7节的观点是一致的。
因此,我再次怀疑:知识抽取器=>的可靠性
有人能清楚地说出暗示证据吗?或者至少给我一点提示?
或者,知识抽取器的存在在某种程度上避免了验证者被认为是不被Prover真正知道的“证人”,所以它可以被认为是一种“可靠的属性”,即使与通常的“证人”性质不同?( Geoffroy Couteau在最初提到的问答交流中似乎证实了这一观点,当时他写道:
是的,健康的味道有几个维度:你是有“成员健全”还是“知识健全”是其中之一(我在论文中通常说‘知识提取性’来区别于通常的稳健性)。
然而,如果是这样的话,我会期望他在OP中纠正这个“暗示”)
抱歉,我说了些话,我希望能用一种可以理解的方式来描述我的疑虑。
发布于 2022-04-04 09:58:49
知识可提取性是一种比稳健性更强的属性。下面,我将勾勒出为什么无条件的知识提取意味着统计的稳健性。从非正式的角度来看,统计的稳健性说明:
如果陈述不正确,那么任何恶意证明者产生接受证据的可能性都是微不足道的
另一方面,KE指出:
(*)“采取任何(可能是恶意的)证明算法,该算法以不可忽略的概率产生接受证据,然后有一个(预期多项式时间)提取器与该证明程序交互作用,并恢复该陈述的真实性的证人(即证明)”。
如前所述,应当相对清楚地表明,KE意味着健全:如果保证KE能找到一名陈述属实的证人,这尤其意味着该陈述是真实的。在其他方面,(*)意味着:
如果有一个(可能是恶意的)验证程序算法,以不可忽略的概率产生接受证明,那么这个陈述就必然是正确的
对立面是这样的:“如果陈述不正确,那么任何证明算法都不能产生不可忽略的概率的接受证明”,
这正是统计上的稳健性。请注意,这并不能给您提供完美的可靠性:为此,您需要一种“超级强”知识可提取性,这将确保从任何(可能是恶意的)验证程序中提取出具有任何概率p>0的接受证明。
请注意,在某些情况下,我们只能证明KE的计算形式,例如“我们可以从这个多项式有界的成功证明器中提取一个见证,或者我们可以使用这个证明程序来解决这个难题”。在这种情况下,计算KE意味着计算的稳健性。
发布于 2022-04-05 08:12:08
谢谢!现在,您的素描帮助我不再迷失在FoC 4.7的正式细节中,也帮助我理解了当知识的稳健性意味着健全,它是同时发现的,值得在这里引用,我想(这也是我写这个作为答案的原因)。
我认为我的困惑首先是因为我不是这一领域的专家;-)后来戈德里希热衷于选择不定义虚假陈述的KE有效性,以及他对不能处理虚假陈述的推论(即使你的素描使我认为,即使在这种情况下没有定义,似乎也不可能返回虚假陈述的不存在的证人,因此KE返回证人确实意味着陈述是真实的,因此在Goldreich的假设下,您的逻辑链似乎也是有效的)。
https://crypto.stackexchange.com/questions/99448
复制相似问题