爱丽丝是色盲的。她永远不知道自己的手套是否匹配。她的弟弟鲍勃（Bob）总是嘲笑她说手套不匹配，所以应该去换手套。爱丽丝想知道鲍勃是否在说关于她的手套的真相。

假设爱丽丝只有两种颜色的手套，她如何设计可以与之配合使用的
协议？她的兄弟来确定Bob是真实的还是在取笑她？


我认为Bob在一开始就决定是取笑还是诚实。如果取笑，他会随机选择自己的回答。

我的直觉告诉我，这个问题类似于电话问题上的投掷硬币……但是我似乎无法建立一个爱丽丝能够解决的方案知道他是否在说实话，她无法核实吗？我正在为期末考试而做的任何帮助，将不胜感激！

#1 楼

这是一个经典的例子。

这里是证明系统……

Bob给Alice戴了两副手套，所以每只手都握着一只。此时Bob可以看到手套，但是Bob并没有告诉Alice哪一个。爱丽丝然后将双手放在背后。接下来，她要么在双手之间切换手套，要么让手套原样摆放，每个概率为$ 1/2 $。最后，她从背后将它们带出。鲍勃现在必须“猜测”她是否换了手套。

通过看着它们的颜色，鲍勃当然可以肯定地说爱丽丝是否换了手套。另一方面，如果它们是相同的颜色，因此无法区分，则Bob不可能以高于$ 1/2 $的概率正确猜测。

如果Bob和Alice重复此“证明” $ t $次（带有较大的$ t $），Alice应该确信手套的颜色确实不同。因为如果它们具有相同的颜色，则Bob能够成功识别所有开关/非开关的可能性最多为$（1/2）^ {t} $。

（此外，证明是“零知识”，因为爱丽丝从不知道哪种手套的颜色是什么；实际上，她不知道如何区分手套……但是证明系统对她有所帮助。）

如果任何人在理解零知识证明时遇到问题，我想指出“零知识技术（PDF）”（PDF），其中包含与我相似的色盲示例，以及还有更多解释ZKP的示例，包括Jean-Jacques Quisquater的示例，该示例已发布在“如何向孩子解释零知识协议”（PDF）中。那应该有帮助...

评论

$ \ begingroup $
在您的协议中，即使Bob最初给Alice提供了不同颜色的手套，他也可以向Alice证明它们是相同颜色的，对吗？因为，当爱丽丝问她是否要换衣服时，鲍勃只是无视手套，而是抛硬币回答。
$ \ endgroup $
–satya
19 Mar 7 '19 at 2:59
$ \ begingroup $
@satya这是一个太宽泛的问题，无法在这里回答。请考虑改为发布问题。您的评论和此评论将在周末删除。
$ \ endgroup $
–马腾·博德威斯♦
19年3月8日在11:43
$ \ begingroup $
@satya：让我们进入这个问题的非零知识变体：Bob指着绿色手套说“这只手套是绿色的”，可以证明他不是色盲的。不会始终通过此测试。现在，让我们假设鲍勃声称他是色盲的，然后有意地指着一个红色的手套并声称它是绿色的。爱丽丝不知道他在说谎。说谎者可以通过忽略他们的知识来简单地模拟无知。说谎者不能通过证明知识来模拟知识。
$ \ endgroup $
–布赖恩
19年5月24日在20:59