作者LPH66 ((short)(-15074))
看板puzzle
标题Re: [请益] 请问有人知道关於各类魔方的零知识吗?
时间Fri Oct 17 01:34:04 2008
好像离版题远了些
不过有人问到了这个 所以回个文
※ 引述《joeyeh (joe)》之铭言：
: 推 aegius1r:可以解释一下零知识吗@"@? 10/16 23:15
所谓"零知识证明"
是指一个人P宣称他知道某件事
他想说服另一人V说他知道某件事 但不想告诉V有关这件事的细节
P所用来向V证明的方法(或说两人之间的互动过程)就叫"零知识证明"(或称零知识协定)
这证明要成立有三个条件:
(1) 完整性: 如果P果真知道这件事 那照这个方法做的V会被说服P的确知道
(2) 健全性: 如果P其实不知道这件事
那照这个方法做的V除了极小的机率之外都可以抓包
(3) 零知识性: 如果P果真知道这件事
那V除了知道「P知道这件事」是真的之外一无所知
(包含所谓"这件事"的细节)
我在前篇推文说要应用在「难」的问题上是表示说
V不会由证明的过程推出P所知道的东西是什麽 (从而知道了V不该知道的东西)
例如: (这是英文维基上的例子)
现在有一个洞窟 里面岔成两条路 在後面连起来 但有一个魔法门隔开
P现在宣称他知道怎麽开这个魔法门 他想在不告诉V怎麽开门的情形下说服V
这里 「开魔法门」就是那个「难」的问题的类比
P和V都知道有魔法门 但只有P知道怎麽开
这个"零知识证明"如下:
首先 P先进洞 V在外面 然後P随机选一条岔路进去
接着V进来 大喊着要P从哪条路出来(也是随机选)
看看P是否真的从那条路出来
重覆这个过程至少十几二十次 如果P每次都能照所喊的出来
那"P知道怎麽开门"这件事就非常有可能是真的
因为如果P知道 那P一定可以每次都照所喊的路走出来
如果P不知道的话 他只会有1/2的机率猜中答案从所喊的路走出来
因此如果真不知道 重覆20次都猜中的机率就是一百万分之一了 符合条件(2)
因此在够多的次数之下 V会被说服P的确知道怎麽开门 符合条件(1)
而且这过程中 V完全不会知道这门怎麽开
他除了"P知道怎麽开门"之外什麽都不知道 符合条件(3)
---
这东西的用途主要是在密码学
P要向V证明他有某个东西(例如RSA的密码) 但不能给V知道这个东西是什麽
他就可以用和这个类似的过程来向V证明
---
上面说的只是概念
尤其条件(3)里所谓"除此外什麽都不知道"是个满抽象的词
是有个定义来定性描述这件事 不过我还没搞懂 @_@
--
実琴：「
河野！你真的就这样被
物质慾望给吸引过去了吗?!」
亨：「只要
穿着女装摆出亲切的样子，所有必要花费就能
全免，似乎一点都不坏啊。」
実琴：「难道你没有
男人的尊严了吗?!」
亨：(断然道)「
没有。在
节衣缩食且
生活吃紧的
学生面前，
没有那种东西。」
－－プリンセス・プリンセス 第二话
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.250.80
1F：→ joeyeh:讲白一点就是V得到的就是单向杂凑的结果,但他知道结果是合 10/17 07:44
2F：→ joeyeh:理的范围,但他完全不知杂凑函数,所以他没有机会可以推知 10/17 07:46
3F：→ joeyeh:举例,某使用者在伺服器A和伺服器B都有使用权,也在两伺服器 10/17 07:51
4F：→ joeyeh:都有各个设定的密码,当使用者登入伺服器A想使用伺服器B的资 10/17 07:53
5F：→ joeyeh:源时,就必需得到伺服器的信赖,此时A就会向B证明此user已验 10/17 07:54
6F：→ joeyeh:证过,让B不用重覆验证此user,但两伺服器却一点也没办法得知 10/17 07:56
7F：→ joeyeh:存在两者各自的密码,但B确可以信赖A确实验证过user了 10/17 07:57
8F：→ joeyeh:因此B会让user直接使用B的资源而不用再次验证. 10/17 07:58
9F：推 keepaway:看起来满好玩的 10/17 11:43
10F：推 geken:很有趣的问题 10/17 13:59
11F：→ joeyeh:去MIT找一下Kerberos计划,里面有些有趣的问题喔 10/17 17:45
12F：推 aegius1r:大概了解了 谢谢XD 10/17 18:45