我刚刚意识到我很难区分这两个术语(知识证明和零知识证明),特别是在许多加密协议中似乎只使用后者的情况下。

零知识证明通常被定义为证明者设法向验证者证明给定语句为真的方法,除了该语句为真的事实外,不透露任何其他信息。例如,假设我想证明我所生成的某些密文的明文知识,以便每个人都可以检查明文是否具有某种形式(例如,在一定范围内的值)。在我看来,在这种情况下,我很想使用零知识证明,因为我不希望其他人学习我的明文是什么,或者我曾经使用过哪个随机值对其进行加密(我假设我使用了公共密钥加密方案。

另一方面,知识证明似乎只是定义为证明者说服验证者他/她知道某事的那些证明(没有说明任何事实)。关于验证者可以从与证明者的交互中学习或不能学习的知识的约束。从定义来看,这两个术语似乎有很大的不同。但是,我发现很难看到在哪种情况下人们会只使用知识证明而不是零知识证明。

评论

零知识证明通常是交互式的。在非交互式环境中使用知识证明会更容易。

#1 楼

从形式上来说,这都是非常复杂的,但从非正式角度来说,这是非常复杂的:

交互式证明是指证明者与验证者之间的对话,其结果是验证者接受或拒绝。

交互式证明可以是零知识,在这种情况下,作弊验证者无法通过与诚实的证明者交谈来学习任何新知识。

交互式证明可以是知识的证明,其中作弊证明者无法说服某人。除非他(本质上)知道某些秘密,否则诚实的验证者必须接受。

交互式证明当然可以是零知识和知识证明。

评论


$ \ begingroup $
感谢您的回答@ K.G,但是您是否知道使用知识证明而不是零知识证明的任何示例,上下文或情况?因为在我看来,只要有人想证明某件事,最好总是以零知识的方式来做。是对的,还是实际上在某些情况下,我们可能更喜欢知识证明而不是零知识证明?
$ \ endgroup $
– LRM
13年9月30日在13:44

$ \ begingroup $
有没有证人的证据。但是您是对的,通常您想要某种零知识的变体,因为如果您不关心秘密输入的秘密,您可以公开输入。零知识和知识证明仍然是两个不同的概念。
$ \ endgroup $
– K.G.
13年9月30日在13:49

$ \ begingroup $
知识证明例如用于证明活板门的知识。如果考虑元素$ y $到某个基本$ x $的离散对数,则想证明自己知道$ \ log_x y $。但是显然,在这种情况下,您还希望证明为零知识,或者您可以声明解决方案并说“就是这样,这是我知道解决方案的证明”。
$ \ endgroup $
– tylo
2014年11月25日15:08



#2 楼

$
\ newcommand {\ NP} {\ mathbf {NP}}
\ newcommand {\ coNP} {\ mathbf {coNP}}
\ newcommand {\ TFNP} {\ mathbf {TFNP }}
\ newcommand {\ L} {L}
\ newcommand {\ R} {\ mathcal {R}}
$

零知识证明知识的知识在纯零知识证明的概念是虚无的情况下很有用。我认为接受的答案有点忽略了这一点(关键)。例如,考虑一下$ \ NP \ cap \ coNP $中的硬语言$ \ L $。即$ \ L \ in \ NP $和$ \ L \ in \ coNP $,或等效地为$ \ L,\ bar {\ L} \ in \ NP $。根据定义,有两个(有效可验证的)$ \ NP $关系$ \ R_0 $和$ \ R_1 $分别对应于$ \ L \ in \ NP $和$ \ bar {\ L} \ in \ NP $ 。接下来,考虑“组合的” $ \ NP $关系
$$ \ R = \ R_1 \ cup \ R_2:= \ {(x,0w):( x,w)\ in \ R_0 \} \ cup \ {(x,1w):( x,w)\ in \ R_1 \}。$$
请注意,与$ \ R $相对应的决策问题是微不足道的,因为每个字符串$ x $都有一个$ 0 $见证人或$ 1 $见证人。这也意味着对于$ ​​\ R $来说,零知识证明是虚空的,因为每个$ x $都在句法上保证了证人的身份-验证者没有必要了解证人的存在。例如,这与$ SAT $不同,在$ SAT $中,字符串$ x $可以有见证人也可以没有见证人。$ ^ 1 $在这种情况下,见证人的存在(即,令人满意的陈述)对验证者而言并非无关紧要。 $ ^ 2 $。另一方面,$ \ R $的知识证明会完成一些不平凡的事情,因为它使验证者确信证明者是证明者实际上认识证人(通过提取者)。

事实证明,与密码学中的某些(计算)困难问题相对应的决策问题具有上述形式,因此比较琐碎。这些恰好对应于$ \ TFNP $中的搜索问题,$ \ TFNP $是所有$ \ NP $搜索问题的类别($ \ NP \ cap \ coNP $的搜索对等物)。一个这样的例子是素数阶$ p $的(循环)组$ G $中的离散对数问题。给定一个生成器$ g $和一个元素$ h \ in G $,我们知道存在$ a \ in \ mathbb {Z} _p $这样$ g ^ a = h $。因此,零知识是微不足道的。但是证明者可以使用Schnorr协议说服一位Verifer知道离散对数的知识。有趣的是,正如该主题指出的那样,我们知道的最有趣的零知识证明也证明是知识的证明。

$ ^ 1 $这是$ SAT $很难使用的原因之一。这是一个大海捞针的问题,我们甚至都不知道大海捞针是否存在。

$ ^ 2 $虽然这个证人仍然很难找到。因此,与$ \ mathbf {P} $中的语言不同,有一些不容易学习的东西。

#3 楼

一个交互式证明系统,包括一个具有零知识特性的系统(一个零知识证明),用于识别一种语言。也就是说,要确定输入是属于子集还是整个集合(宇宙)。
知识证明是具有知识提取器算法的交互式系统。

现在考虑Pedersen的承诺,其中任何组元素都可以是有效承诺。这意味着“是一种承诺”的语言就是宇宙本身。用于此承诺方案的$ \ Sigma $类型的协议具有知识提取器,该知识提取器具有与组顺序相反的知识错误。

随后,知识证明是用于证明有关使用Pedersen承诺提交的数据的语句的合理工具。方案,但不是交互式证明系统。