首页 >> 计算机科学 >> 文章

战争中你被俘了,敌人拷问你情报。你是这么想的:如果我把情报都告诉他们,他们就会认为我没有价值了,就会杀了我省粮食,但如果我死活不说,他们也会认为我没有价值而杀了我。怎样才能做到既让他们确信我知道情报,但又一丁点情报也不泄露呢?

这的确是一个令人纠结的问题,但阿里巴巴想了一个好办法,当强盗向他拷问打开山洞石门的咒语时,他对强盗说:“你们离我一箭之地,用弓箭指着我,你们举起右手我就念咒语打开石门,举起左手我就念咒语关上石门,如果我做不到或逃跑,你们就用弓箭射死我。”

强盗们当然会同意,因为这个方案不仅对他们没有任何损失,而且还能帮助他们搞清楚阿里巴巴到底是否知道咒语这个问题。阿里巴巴也没损失,因为处于一箭之地的强盗听不到他念的咒语,不必担心泄露了秘密,而且他确信自己的咒语有效,也不会发生被射死的杯具。

强盗举起了右手,只见阿里巴巴的嘴动了几下,石门果真打开了,强盗举起了左手,阿里巴巴的嘴动了几下后石门又关上了。强盗还是有点不信,说不准这是巧合呢,他们不断地换着节奏举右手举左手,石门跟着他们的节奏开开关关,最后强盗们想,如果还认为这只是巧合,自己未免是个傻瓜,那还是相信了阿里巴巴吧。

“零知识证明”说的是示证者向验证者表明他知道某种秘密,不仅能使验证者完全确信他的确知道这个秘密,同时还保证一丁点秘密也不泄露给验证者。阿里巴巴的这个方案,就是认证理论“零知识证明”的一个重要协议。

除了被俘后如何靠情报保命这个问题,零知识证明在社会领域中还有着很多应用场合。例如你证明了一个世界级的数学难题,但在发表出来之前,总是要找个泰斗级的数学家审稿吧,于是你将证明过程发给了他,他看懂后却动了歪心思,他把你的稿子压住,把你的证明用自己的名义发表,他名利双收,你郁闷至死,你去告他也没用,因为学术界更相信的是这位泰斗,而不是你这个无名之辈。

这并不是天方夜谭,而是学术界常见的难题,前些年有个博士生告他的泰斗级导师剽窃他的成果,但除了令师生关系恶化外没有任何效果,最后他使出了撒手锏,称他在给导师审阅的论文的关键公式中,故意标错了一个下标,而这会导致整个推导失败。学术委员会一查果真如此,但还是有倾向于泰斗的声音,有人说那是泰斗的笔误,只不过让你发现了而矣,并不能证明那公式就是你推导出来的。

这个博士生故意标错下标,不能说他没有心眼,但他没有把“零知识证明”理论用好,以致于落到这种地步。“零知识证明”早在1986年就被A.Fiat和A.Shamir用数学的方法给出了解决方案,并在同年申请了美国专利,但由于该理论可能被用于军事领域,专利局被军方密令搁置,6个月后,军方命令:“该申请发表后会有害于国家安全......所有美国人的研究未经许可而泄露将会被判刑罚款”。看来军方认为作者肯定是美国人了,但作者实际上是在美国申请专利的以色列人,研究也是在以色列的大学里做的,军方这个命令摆了个大乌龙,虽然两天后撤消了,但已经成为了学术界的笑柄。

这个笑柄也说明了一个问题,即“零知识证明”非常重要。基于数学的推理虽然非常复杂,但思路却很简单,上述的阿里巴巴方案就是其中之一。其它的一些方案,也都是像这样遵循着分割和选择(Cut and Chose)协议的。

例如图论中有个哈米尔顿回路(Hamiltonian Cyclic)问题,说的是多个顶点的全连通图,若有一条通路通过了所有顶点,且每个顶点只通过一次,那这就是哈米尔顿回路。如果顶点较多的话,即使用计算机穷举计算很难找出这条回路,因为通路的可能性真在是太多了。

如果松鼠会贴了一张全连通图(命名为A图)悬赏哈米尔顿回路,而且任命我(奥卡姆剃刀)作为评审官,你幸运的找到了一条,那该怎么办呢,将结果直接发给我吗?千万不要,因为保不齐我会将你的成果让给了我的亲信。那你该怎么办呢?应该这么办:

1、你将A图的顶点搞乱了,并生成一张新图,只是顶点的位置变了,而新图顶点之间的连线关系与A图是完全一致的。这时,新图中每个顶点与A图中每个顶点的对应关系你是清楚的,而且新图中的哈米尔顿回路你也是知道的。

2、你将这张新图发给我,没错,就是仅仅一张新图,上面并没有画着你发现的牛B回路。

3、我收到后,对你提出两个问题中的一个:一是证明新图就是从A图变形过来的,所有顶点和连线的关系完全一致,二是画出新图中的哈米尔顿回路。

4、如果你真的找到了A图的哈米尔顿回路,这两个问题当然都能轻松回答。需要注意的是:你只需要回答第3步的其中一个问题,千万不要两个问题一并回答,否则我就知道你关于A图的哈米尔顿回路了,你就SB了。

5、我还是不相信你,因为有可能你只是将A图变了形,却根本不知道A图的哈米尔顿回路,而我在第3步时恰好要求你证明新图就是从A图变形过来的,你当然能证明。或者有可能你找了个你知道哈米尔顿回路的图,但这张图跟A图一点关系都没有,而我在第3步恰好要求你画出这张图的哈米尔顿回路。

6、我要求你从第1步开始重复这个验证过程,随着次数的增加,第5步那种巧合的可能性就越来越低,如果你多次能回答对第3步中的问题,那我还不相信你已经找到了A图的哈米尔顿回路,那我就是一个傻瓜。

7、为了表明我不是傻瓜,我在松鼠会群博里宣布你找到了A图的哈米尔顿回路,而这时我并没有看到你所画的A图的哈米尔顿回路。

回到你证明了世界级的数学难题的问题,你可以用这种分割和选择协议来进行零知识证明,来保护你的权利。你公开声称你解决了这个数学难题后,验证者会给你出一个其它的题,而能做出这道题的前提条件是已经解决了那个数学难题,否则的话无解,而且这个条件是学术界所公认的,这个题就是所谓的平行问题。不出所料,你靠着已经解开数学难题的基础把这个平行问题做出来了,但验证者还是不信,他又出了一道平行问题,你又做出来了,多次较量后,验证者就确信了你已经解决了那个数学难题,虽然他并没有看到具体的解法。

大家已经看出来了,零知识证明需要示证者和验证者的密切配合,但如果你只是一个数学界的无名之辈,即使你宣称你解决了数学难题,也不会有人跟你配合着玩零知识证明,那你该怎么办呢?

我告诉你一个可以在法庭上都能当作有效证据的招数,你将证明打印好,选择一个最可靠最权威的邮政公司,把它寄给自己,当你收到这个扣着邮戳的包裹后,不要打开,把它放好,然后就可以把证明寄给数学泰斗。如果他用自己的名义发表了,不必着急,等他依靠其影响力把这个证明炒热后再出手,你上法庭控告他,他当然不承认,在法庭上你将那个没开封的包裹拿出来,上面清清楚楚地盖着时间戳,这就证明了你包裹里的证明是发生在那个时间戳之前的,加上之后的你邮给泰斗论文的邮件存根,和泰斗以自己名义发表论文的时间,三者就构成了一个完整的证据链,泰斗灰头土脸名声扫地,而你大获全胜名利双收。

参考文献:《通信网的安全-理论与技术》,王育民等编著,西安电子科技大学出版社,2000.5

0
为您推荐

151 Responses to “阿里巴巴的零知识证明”

  1. 老张说道:

    发表时间好像超光速了:)

  2. 王源说道:

    看完之后觉得好阴险好诡异好扭曲啊

  3. hoxide说道:

    为什么不用 arxiv ?

  4. beiang说道:

    我告诉你一个可以在法庭上都能当作有效证据的招数,你将证明打印好,选择一个最可靠最权威的邮政公司,把它寄给自己,当你收到这个扣着邮戳的包裹后,不要打开,把它放好,然后就可以把证明寄给数学泰斗。如果他用自己的名义发表了,不必着急,等他依靠其影响力把这个证明炒热后再出手,你上法庭控告他,他当然不承认,在法庭上你将那个没开封的包裹拿出来,上面清清楚楚地盖着时间戳,这就证明了你包裹里的证明是发生在那个时间戳之前的,加上之后的你邮给泰斗论文的邮件存根,和泰斗以自己名义发表论文的时间,三者就构成了一个完整的证据链,泰斗灰头土脸名声扫地,而你大获全胜名利双收。

    ——————————————————————————

    这招有人试过了么?好奇~

    • Mao说道:

      这个方法我之前看过,说是游戏策划者在拿出去募资和销售给大型出版公司时,可以用这一招。当时的提法是这个有判例先例

    • yangxing说道:

      貌似这个办法忘记了最重要的一点,泰斗为什么要承认这稿件是你寄给他的?也就 是说,自己研究出的东西完全可以说你是偷袭我的,然后拿我的东西复印寄给你。

      • 说道:

        科学泰斗虽然可以否定说是我自己想的,但是小伙子有寄给泰斗的票根,给他寄过东西呀。

      • dbgwalter说道:

        实际上邮件存根可以说明邮寄物品,也可以选择收件人签字收取这种方式来获得收件人的验收签名。如果对方否认的话,他需要自己举证,曾经收到的东西与本案无关。或者举证,是寄件人在更早的时候剽窃了他的成果,如果他无法拿出证据,法庭是不予采纳的。

      • MystAE说道:

        只要在加上寄给自己的邮件时间比论文的发表时间早,就已经有足够的说服力了

  5. chandeen说道:

    受益匪浅!谨受教!

  6. vip说道:

    已阅,沙发

  7. 野草博客说道:

    希望所有搞研究的后生们都学会这个绝招……

  8. 西河说道:

    这个问题在计算机网络层如何实现呢?

    • hongzhen_xu说道:

      公钥和私钥加密、数字签名可以实现网络零知识证明。

  9. 打破的管道说道:

    不妨多找几家权威的邮政公司,而不是把赌注都压在一家上。
    不知给自己发电子邮件是否有法律效力?

  10. 花大大说道:

    现在不是有公证处吗,拿到公证处去公证下,在寄出去不就行了吗?

  11. bk201说道:

    厉害!

  12. 刘冲说道:

    大家好,已阅

  13. Wintermute说道:

    很多黑客在渗透成功,在首页上涂改的时候也面临类似的问题:既不能留下明显、真实的个人信息,以防被抓到;又必须留下和自己相关的信息,向圈内人证明能力。于是就会留下一串只有他自己知道的字符串的MD5 HASH。

    • logicthief说道:

      这个办法也有一定风险,因为教授也能想到,他会把所有可疑的过程进行变换,博士想要瞒过他挺难的。

      • rayiooo说道:

        可以用“答案+一串随机数或者自己的口令”的hash值代替“答案”的hash值

  14. biohu说道:

    果然好办法~~

  15. wonseberg说道:

    佩服佩服

  16. 伊藤博文说道:

    果然!剃刀大叔是坏淫!大坏淫~心里不藏点儿好~尽是歪招~

    • 奥卡姆剃刀说道:

      谢谢表扬,准备下周写篇关于电影《无间道》中卧底身份的歪招,欢迎关注。:)

  17. newgnaw说道:

    哈哈,好玩好玩!
    话说项目申请和论文评审的时候很可能出现这种坏人哦

  18. 四月说道:

    好厉害吖…

  19. 芝麻开门崔玲说道:

    这招不错,教会人把事情想得更加周全一点

  20. nobody说道:

    可以再详细说说遵循着分割和选择(Cut and Chose)协议嘛,有一个通用的方法吗?

    • 奥卡姆剃刀说道:

      再详细写就涉及到麻烦的数学了,就不好看了。方法有很多,并不通用,但这种分割与选择的思路是一致的。

    • laozizhitu说道:

      这个cut-and-choose技术是为了实现公的一个方法,来源于两个人想共同分一块蛋糕,但是每个人都想自己得到最大块。解决的方法是:第一个人先用刀把蛋糕切开,第二个人首先选择一块,剩下的一块就归第一个人所有。因为每个人都想自己分的最多,别人分得最少,所以最终结局是第一个人肯定会恰好把蛋糕切成均匀两半。

  21. nobody说道:

    还有现在强盗手里有枪,又怎么办呢?

  22. kiteinsky说道:

    这招太好玩了,哈哈

  23. farewell说道:

    最后那个确实是好办法 嘿嘿

  24. 知一说道:

    剃刀大叔的歪招真多啊!

  25. Welcome to the English blog

  26. 杨明华说道:

    很好的话题,教会我们保护自己的知识产权!

  27. 贝卡利亚说道:

    何须邮政,公证不就可以了么?

  28. 星期五13说道:

    提供个案例,^_^在种田农民哪里看来的,nature review 的08年发表的文章抄袭10年的文章。http://blog.sina.com.cn/s/blog_4abe58910100iu9a.html

  29. jcding说道:

    在设计或者创意的领域有没有类似的方法可以避免剽窃呢?比如说有些公司征集logo设计或者是营销策划之类的

    • 任子爵士说道:

      对哦,关于平面设计,尤其LOGO这种有好办法木有呢?

    • Kenko说道:

      可以使用水印技术。简单说来就是在原来的jpg图像中修改多个像素的数值,从而隐藏了个人信息。但从人肉眼看来,修改后图像的颜色几乎没变化。
      这样,这个图片就包含了你个人的签名信息了。

      当然,如果你那个logo投稿给人家,然后人家照着你这个,自己重新画一个,那就没办法了。
      但如果他只是复制你的图像,就可以按照水印技术的办法查出来。
      详细可以联系我kenkofox@qq.com,我有朋友做这方面的研究。我是研究生。

      • nb lady说道:

        希望你们快点研究出设计这一领域,剽窃现象特别严重,光加水印防止不了

  30. fan说道:

    不赞不行啊!期待剃刀叔的“无间道”,上次的举得“象棋大师”的例子也很强大。

  31. 百丽女鞋说道:

    阿里巴巴确实很牛啊!

  32. 淘宝网首页说道:

    不错,学习了。。

  33. 真卓说道:

    学到了,以后就用此招对泰斗了!呵呵!

  34. PS说道:

    我就想起了twi tter的oauth登录

  35. 10086说道:

    好文!我在你说论文时想到的第一个办法就是自己把论文先封存起来,做公证,然后以备万一,没想到你在最后说了,哈哈。

  36. Lv说道:

    我对这篇文章有两个疑惑。
    第一,哈米尔顿回路,不管第五步重复多少遍,在我找到A图回路这个问题上,都是不可信的。如果我有两手准备,能把A图无限变形转化成同类型图,且掌握无限多非A图的哈米尔顿回路,单凭这两点,不管你让我重复多少回,我都能轻松应对。但事实上,我根本没有找到答案。
    第二,找邮局寄给自己,我个人觉得这根本不能算是什么证据吧。公证一下,顶多是给自己吃个定心丸。你只能证明在教授发表疑似是你观点的论文前,你手上就有相似的东西。大家都有,凭什么说我抄你,就凭你自己寄东西给自己的邮戳?

    • 奥卡姆剃刀说道:

      第一,哈米尔顿回路问题,你的两手准备的确都是可以无限的,假如你给了我一个变形图,但你并不掌握该图的哈米尔顿回路,我收到后,对你提出两个问题中的一个:一是证明新图就是从A图变形过来的,所有顶点和连线的关系完全一致,二是画出新图中的哈米尔顿回路。如果我让你证明二,你马上就漏馅了。

      当时,我也可能让你证明一,你就侥幸地通过了这此考察。但是,这种验证要重复进行n次,你不可能每次都这么侥幸,随着n的增大,你能忽悠我的可能性就呈指数级的急剧减少,即(1/2)^n。

      第二,不可能大家手上都有相同的东西,否则的话,那也不能算作你的原创了。

      • 游客说道:

        ems 公证送达,就可以了,没这么麻烦

      • Lv说道:

        你说的对,关于第一个问题,我明白自己逻辑哪出问题了。
        但关于认证问题,我觉得还有待思量。比如你需要我帮你审核论文,再次之前你邮寄给自己了一份,当我阅读了,意识到你研究的突破性,在交换与付你之前,记录下你的核心思想(假设我手上也做着类似的工作),以最快的速度修改所有你的个人语言特征,并绞尽脑汁用各种琐事来拖延你发表文章(要做就做的彻底嘛),直到我先于你发表这篇论文。也许这个故事的结局就像你所提到那个修改下标的事情一样。
        我个人认为,防止这类悲剧发生的一个有效途径,就是导师审核论文的公开化,告别过去两人互动的局面,打开网站,所有人都能看到某知名教授正在查阅谁谁谁的论文,挺明白的。当然这只是我的胡思乱想

      • 梦里有风说道:

        我觉得用邮戳那个方法还是值得商榷。你的确只能证明教授发表之前,你已经有了类似研究,但是不代表是你原创,教授可以说他创作的比你还早,只是在发表之前已经跟你讨论过或者以其他形式让你参与过研究。你拿出邮戳证明,只能说明在教授正式发表之前你已经有了一份资料,但是教授具体何时得出成果的你无法证明,除非你有办法证明他得出成果的时间比你邮戳时间晚~否则所谓的证据也是白搭

  37. 春歌的猫说道:

    嗷嗷的好玩

  38. 单词帝说道:

    此方法在天朝真的有效?寄给自己……

    • GARNDIA说道:

      也许半路上就被莫名其妙的弄不见了...包裹丢失,损坏,漏水..各种抓狂,呵呵

  39. 曾小泽说道:

    好有趣的理论~~~~~~

  40. 烫小卷说道:

    受益匪浅 寓教于乐

  41. 秋天小鱼说道:

    膜拜大叔,大叔好有知识,我要看书去了

  42. 淬念说道:

    这个问题解决了我长期以来的一个困扰。

    事实上,我已经攻克 了数学界的王冠,哥德巴赫猜想!

    但是,我是无名之辈,苦于泄密和被”泰斗专家“戏耍的危险,才”按下不表“

    明天,大家可以从互联网,电视中发现,我已名扬宇宙。趁现在我还没出名,大家可以给我发邮件免费索取签名,本泰斗(未来的泰斗)从看完此文开始的24小时内,刨除吃喝拉撒的时间,只签大约7到8个小时。过期不候。

  43. 沿见说道:

    害人之心不可有,防人之心不可无啊

  44. 二十六公斤说道:

    阿里巴巴,已经成功了···

  45. 珊水33说道:

    解释的过程很曲折,解决的方法很简单,哈哈,受用了

  46. [...] Shared 阿里巴巴的零知识证明. [...]

  47. horseluke说道:

    “找邮局寄给自己”的问题似乎还是比较难以解决,因为现代社会,似乎连发稿都是用电子版的,这种情况下,谁来公证?

  48. schwartz说道:

    汉密尔顿回路的例子很好,但是寄包裹给自己的办法有局限性.
    给自己的包裹上的时间戳只能证明你在那一刻有了证明的方法。给泰斗的邮寄存根只能说你给泰斗看过你的证明。泰斗完全可以说他/她在那之前已经有了该证明(只不过没有发表)。
    除非整个学术界规定所有人一旦有任何想法都必须先把该想法打印出来再盖上时间戳,否则这个办法还是防君子不防小人

    • GARNDIA说道:

      恩,我也同意你说的想法
      不过貌似公认都是谁最先发表,就是谁的吧
      因为不可能因为你先"想"到的而判定是你的,不论什么原因拖延了自己的发表时间,某种意义上讲还是别人赢了,这也没有办法的事,呵呵

  49. Kelvin说道:

    确实很有道理

  50. 小英雄说道:

    我先在网上发表,然后再拿去投稿,时间已经被网站记录,同时也被网友看到,不就行了 ?

    • KBT烟火说道:

      这是个待审核的证明,直接发表在网上,是否不妥?如果每次都发不确定的东西,个人可信度是不是会下降

  51. 我思故我在说道:

    够强!道高一尺魔高一丈!

  52. Eldorado说道:

    很多顶戴花翎的“学者”在什么学校挂个职,然后就是其他老师教授什么的安排一些学生给这人做课题发表出来,根本用不着背地里盗用,因为已经正大光明的窃取了,腐败的大学。。。。。。

    • fstone说道:

      如今时代还用剽窃吗,都送上去还要看人家中意不中意哪!

  53. shen sun说道:

    Very good idea! 电子邮件可以试,但比较麻烦.从邮局走,是最好的办法.既然已有成功的例子,就没必要另找窍门了.

  54. judy说道:

    受教了,的确很有必要!

  55. 冂土口说道:

    受益

  56. 说道:

    泰斗可以说全世界的人都在研究,就算你能证明你在我发表之前已经有难题的答案,但是没发表也没用。我发表得比你早,成果就是我的。

  57. 幸福的猪已注册说道:

    太阴险狡诈了吧。。。这活脱脱就是一幕学术界潜规则啊。。。

  58. LCC说道:

    好主意啊~~~~~

  59. aldapple说道:

    让我们更智慧一点点!

  60. ladanseur2010说道:

    真是既有专业知识又有法律头脑,文理通吃啊!

  61. netfrog说道:

    最后那招好像在哪个电影里看到过啊

  62. 若飞说道:

    剃刀大叔好阴险……
    不过防人之心不可无呀!

  63. 花衣说道:

    很好

  64. 筋斗云说道:

    邮戳是很容易伪造的。
    现在都是PGP 的加密算法,你把加密后的内容传给N(N>1)人,然后把未加密内容发表。因为加密算法的不可破性,只需要时间证明,保证了原创。

    这篇文章观点不清晰,没有一个明确理论,没有一个科学界定(到底几次才安全),又没有一个理论不成立的断点的说明。(比如:如果强盗中有一个读唇语的。)(比如:后面AB图转换和B图线路就可能被专家解读从而推导出原解决办法)。
    另外这后面的文章依然没有办法说明最初关于敌人和情报的问题。

    建议作者只针对一个问题来写。写得透彻些。

  65. kk说道:

    学术界为防止被泰斗剽窃,最简单的是到 arXiv 预印本库贴出去,全世界都知道了是你干的,没人敢和你抢了。原因是 arXiv 的公开性以及在学术界公认的公正性。比如证明庞加莱猜想,就是在那里公布的,直到现在都没在任何期刊发表,但数学界都承认是他干的,给他发了菲尔兹奖

  66. ~喵~说道:

    我看懂了。

  67. ~喵~说道:

    我告诉你一个可以在法庭上都能当作有效证据的招数,你将证明打印好,选择一个最可靠最权威的邮政公司,把它寄给自己,当你收到这个扣着邮戳的包裹后,不要打开,把它放好,然后就可以把证明寄给数学泰斗。如果他用自己的名义发表了,不必着急,等他依靠其影响力把这个证明炒热后再出手,你上法庭控告他,他当然不承认,在法庭上你将那个没开封的包裹拿出来,上面清清楚楚地盖着时间戳,这就证明了你包裹里的证明是发生在那个时间戳之前的,加上之后的你邮给泰斗论文的邮件存根,和泰斗以自己名义发表论文的时间,三者就构成了一个完整的证据链,泰斗灰头土脸名声扫地,而你大获全胜名利双收。

    学术界为防止被泰斗剽窃,最简单的是到 arXiv 预印本库贴出去,全世界都知道了是你干的,没人敢和你抢了。原因是 arXiv 的公开性以及在学术界公认的公正性。比如证明庞加莱猜想,就是在那里公布的,直到现在都没在任何期刊发表,但数学界都承认是他干的,给他发了菲尔兹奖
    邮戳是很容易伪造的。
    现在都是PGP 的加密算法,你把加密后的内容传给N(N>1)人,然后把未加密内容发表。因为加密算法的不可破性,只需要时间证明,保证了原创。

    这篇文章观点不清晰,没有一个明确理论,没有一个科学界定(到底几次才安全),又没有一个理论不成立的断点的说明。(比如:如果强盗中有一个读唇语的。)(比如:后面AB图转换和B图线路就可能被专家解读从而推导出原解决办法)。
    另外这后面的文章依然没有办法说明最初关于敌人和情报的问题。

    建议作者只针对一个问题来写。写得透彻些。
    好主意啊~~~~~!

  68. sqj说道:

    最后一个方法只能针对部分情况,比如像文学内容的,因为要想写得一模一样的可能性是几乎为零的,而数学推算之类的,由于其严密性,做到一样是有可能的,并且完全有可能被对手反咬一口说你剽窃了他的。。。就像专利一样,谁先注册算谁的
    敌人和情报的问题。。这个完全是无解的,都要看对象和情形
    任何一个方法获得的结果可能都是多样的

  69. 中式婚礼说道:

    想搞清楚门为什么会听阿里巴巴的

  70. 默小土说道:

    嗯?邮戳好像不是盖在封口的地方哦?

  71. 这个人水平真是太高了,一个文章竟然有那么多的评论。佩服一下。

  72. f。l。y。狂人说道:

    目前我最想知道的是。。。楼主是不是对我们用了。。零知识证明。。。

  73. 随处风流的风说道:

    第一个回路的例子没看懂。但是最后的邮包还是看懂了。学到了很多东西,可以说是举一反三。几乎所有有风险的东西都可以用这个办法解决,是一种保护自己利益的手段。

    不得不说这也算是人类的一种悲哀。

  74. cdlipengfei说道:

    很好的文章,受益匪浅

  75. javie007说道:

    光兄说的太对了
    不是只认发表吗
    数学证明再相似也无所谓,所以权威完全可以说
    啊 原来这个小伙子两个月前也想到这个方法,不过不好意思,我两年前在大便时使劲时就想到了,今天心血来潮所以发表了

  76. cloudhero说道:

    看了这文章,我才知道我还算有点聪明,初中时候上学,有些算术题答不上来,我就用这方法.吓蒙一个答案,往回算,不对就接近点再算,基本试几次就行了,算术题都要四舍五入,所以答案都是正确的,问题是我都没解题过程,老师也为此郁闷.

  77. pangniu说道:

    文中介绍的是Interactive Zero-Knowledge Proof,阿里巴巴和强盗之间需要多次通信。如果双方的通信比较困难(例如距离很远),那么证明将不适用或难以实现。另外,如果通信次数过多,第三方有可能窃听,并且破解其证明内容(即获得哈米尔顿回路和其对应的A图)。

    目前较新的研究的领域是其扩展: Non-Interactive Zero-Knowledge Proof 。

    • laozizhitu说道:

      你的理解也是有偏差的,non-interactive zero-knowledge 是需要有初始设置的,比如说通信双方共享一个随机字符串等,而这些初始设置是需要双方都信任的一个人帮他们完成的,也是有不足之处的。现在ZK的热点不是NIZK,而是适合更复杂环境的高效零知识协议的实现,比如concurrent non-malleable zero-knowledge, resettable sound resettable zero knowledge. 另外还有些纯粹理论上热点。

  78. celebi说道:

    看完文章,受益匪浅
    也不禁的想起,邮件中的密送和抄送.
    自己却找不出当中的关联性.

  79. 过来看看说道:

    作者也太水太业余了吧?

    “你将A图的顶点搞乱了,并生成一张新图,只是顶点的位置变了,而新图顶点之间的连线关系与A图是完全一致的。”

    按照这个描述,所谓的“新图”,与A图完全是同构的,其实也就是A图。

    语言也很水,适合吹牛,不适合科普。

    • 电视说道:

      你羡慕嫉妒恨吧?

    • laozizhitu说道:

      两个图本来就是同构的,可能作者害怕用专业术语的话,有的人会不懂吧,呵呵。判定两个图是否同构是NPC问题的。

  80. holysure说道:

    这篇文章吧我引领到了科学松鼠会,特来顶贴。

  81. fafucarl说道:

    这个世界就是如此。玩的就是智力。要学会保护自己。

  82. mikiblue说道:

    这是个很有意思的题目啊 也教会了怎么防备别人剽窃自己成果~~~

  83. Sirius说道:

    很牛的文章,不过解释同构上不太清楚。
    以前公司的专利在国内发表没有什么问题,现在确实遇上零知识证明的困境了,谢谢该文及该文的作者

  84. semonijan说道:

    我只是想说,四十大盗举起右手,阿里巴巴那白痴念了芝麻开门,门开了,于是强盗就一箭射死他了……而门还是开着的

    这个例子至少得说有两道门

    • nb lady说道:

      哈哈,我也觉得强盗很白痴啊,门开了把阿里巴巴射死了怎么办?

  85. crazy_piggy说道:

    很NB,其实基本原理很简单,就是把问题一分为二,或者是两个步骤或者是两个方面,这两方合并就可以解决问题。
    只是在论证时,把问题衍生成同类的若干问题,而面对这若干问题,我们只需回答这两个问题中的一个。
    公正者经过若干次提问之后就会认为问题已解决(依据心理学重复相信)

    同学们,你们也不要纠结了,剃刀老师只是告诉我们零知识证明的理论,不要在举的例子上钻牛角尖了。关键是在实际应用当中活学活用。

  86. 我非常喜欢这篇文章!

  87. 二哥我二哥味儿说道:

    估计大家多多的地方很近的软硬件的几乎每持有的

  88. 坏人说道:

    阿里巴巴惨了,会被四十大盗打到生不如死的%>_<%
    那个无名小辈也惨了,会被教授迫害到死的T-T

  89. F说道:

    强盗没有问阿里巴巴开门的暗语,http://www.21pick.com/kids/kid2-dp-albbhssdd.htm,至少这个版本是这样的

  90. 法律人士说道:

    回答上面某楼的问题,现在电子邮件是有法律效力的证据。所以作者落伍了。

  91. 书呆子说道:

    拷问战俘和阿里巴巴完全是两码事,不具有可比性.被拷问的战俘只有两条路走:不说是个死,说了也是个死,只是中间省去了折磨的环节,不存在以证明知道机密而可以不交代来换来生存.

  92. SomeOne说道:

    "没有我你什么也做不成"

  93. kk1374说道:

    好办法~

  94. sstpapa说道:

    很好

  95. sstpapa说道:

    很好

  96. check说道:

    5、我还是不相信你,因为有可能你只是将A图变了形,却根本不知道A图的哈米尔顿回路,而我在第3步时恰好要求你证明新图就是从A图变形过来的,你当然能证明。或者有可能你找了个你知道哈米尔顿回路的图,但这张图跟A图一点关系都没有,而我在第3步恰好要求你画出这张图的哈米尔顿回路。

    这段逻辑弄反了.

  97. 老朱说道:

    我会同时发邮件给多个泰斗,并附上hash值,呵呵呵

  98. gudaoxianhe说道:

    不错,值得讨论。

  99. 山海惊说道:

    好,有意思。

  100. locus说道:

    此文不错,受益了。特顶帖。

  101. 小宝说道:

    受益啊,以前都没想过这些!

  102. Sunny Zhao说道:

    前面看着有点迷糊,最后一招学会了。哈哈。。。。

  103. 某人说道:

    太感谢了,我正在愁这个问题,谢谢,谢谢。

  104. kameSong说道:

    太经典啦

  105. cecilia说道:

    最后这招好像以前有个作家用过。具体的忘了。

  106. 小卡说道:

    关于最后一个,数学泰斗可以说是他先将难题的解决方法告诉了你,然后你在他告诉你解决方法到他发表论文的这段时间中进行了给自己邮寄邮件和给他发邮件的行为,为了占学术成果于己有。

  107. 小卡说道:

    关于阿里巴巴,强盗也可以要求阿里巴巴必须告诉他们口令,否则杀死他,为什么要同意阿里巴巴的要求呢

  108. 不哭死神说道:

    汉米尔顿回路那里没搞懂啊,如果你第一次叫我回答第一个问题,我做了,第二次叫我回答第二个问题,我也照做,那你不是就知道牛B回路了

  109. 林帆说道:

    这其实是一个与密码学有关的知识,受益了。

  110. 遁地小仙说道:

    不哭死神 作者不是说了要重复第一步吗 你每次都要打乱图的
    零知识在公钥中有运用
    受教了

  111. 法治践踏者说道:

    有个更简便的方法。可以将记载有证明内容的文本拿去公证处公证,再寄给泰斗

  112. 秦时月说道:

    可以事先跑得公证处把证明公证一下呀!

  113. nscboy说道:

    互联网上有个玩意教数字证书,还有个叫做时间戳服务器的玩意.说到底还是依靠权威来解决信任问题.

Leave a Reply