转载探索零知识证明系列 | 从「模拟」理解零知识证明：平行宇宙与时光倒流( 二 ) _宇宙知识

好了，这个看起来靠谱多了。接下来一个问题就是，怎么理解「计算不出来信息」这个概念？这看来要对信息进行度量，信息的定义又是什么呢？
我们又引入一个概念——「不可区分性」，来重新表述加密算法的安全性：假设你是一个攻击者，而我有一个加密算法：
你随机产生两段等长的明文， m1=「白日依山尽，黄河入海流」， m2=「烫烫烫烫烫，烫烫烫烫烫」
你把这两段明文， m1 与 m2 交给我
我随机挑选一个明文，不告诉你是哪一个，然后进行加密，产生一个密文 c
我把密文 c 出示给你看，让你猜这个c 究竟是由唐诗加密产生，还是乱码加密产生
如果你用一台计算机来破解c ，在多项式时间内破解不出来，也就是说你没办法区分c的来源，那么就说明加密算法是语义安全的
OK ，理解完「不可区分性」，我们再回到「零知识」，如何证明一个交互式系统是「零知识」呢？首先我们要定义下零知识这个概念。
注：不可区分性是概率意义上的不可区分；在学术上，它可以分为「完全不可区分」，「统计不可区分」，还有「计算不可区分」。在本文中，我们暂时不需要理解这些概念的差别。
遇见模拟器
先开个脑洞，设想在平行宇宙中，有两个平行的世界，一个叫做「理想世界」（Ideal World），另一个叫做「现实世界」（Real World）。我们每一个个体可以在两个平行世界中愉快地玩耍，但是两个世界的普通人无法互相感知，也无法互相沟通。
假设「你」是一个很厉害的密码破解者，而且「你」不是普通人，具备在平行宇宙之间穿梭的能力。而 Alice 有一个地图三染色的答案，你的目的是通过和 Alice 对话来获取地图三染色的答案，会话的过程参考上一篇文章的「地图三染色问题」协议。
继续脑洞， Alice 只存在「现实世界」中；在「理想世界」， Alice 被「替换」成了一个长相与声音一模一样的个体，我们称替身为 Zlice 。下一步，把「你」同时放入两个世界中，但不让你知道是你当前位于哪一个世界。你的两个分身所面对的都是一个 “Alice”模样的人。
再重复一遍，在「现实世界」中，与你对话的是一个真实的，并且诚实的 Alice；而在「理想世界」中，与你对话的是 Zlice （假 Alice）， Zlice 虽然相貌语言与 Alice 并无二致，但差异是， Zlice 并不知道「知识」，即不知道一个三染色问题的答案。
接下来在这两个世界中，你的两个分身将同时与真假 Alice 进行对话。神奇的事情发生了，最终在两个世界中，你的两个分身都被说服了，都经过n轮挑战，没有发现对方作弊，即「你」的两个分身都认为对方确实知道「答案」。换句话说，「你」没有能力「区分」出来自己到底在「现实世界」还是「理想世界」，当然也没能力「区分」和自己对话的究竟是 Alice 还是 Zlice 。不仅如此，对于吃瓜群众我而言，如果把「我」作为观察者放入任何一个世界中，我会和你一样「无法区分」出来眼前的这个长相为 “Alice” 的人到底是真还是假。

转载 探索零知识证明系列 | 从「模拟」理解零知识证明：平行宇宙与时光倒流( 二 )

猜你喜欢

转载探索零知识证明系列 | 从「模拟」理解零知识证明：平行宇宙与时光倒流( 二 )