模拟


安全的定义与不可区分性

首先,一个交互式系统,也就是一个对话,它的「零知识」需要证明。毕竟,现代密码学是建立在严格的形式化系统之上。在证明之前,还需要明确「安全假设」到底有哪些。所谓安全假设,比如我们说一个系统的权限隔离做得无比精确,每一个用户只能看到被授权的信息,但是这基于一个安全假设:管理员账号没有被破解。又比如在手机银行软件里,只能通过短信认证码,才能完成转账功能,这也基于一个安全假设:你的手机 SIM 卡没有被克隆。如果我们深入地分析每一个我们感觉安全的系统,都存在大量的似乎不那么稳固的安全假设。比特币私钥安全吗?比特币账户的安全假设也不少:首先你的助记词不能让别人知道,手机钱包里私钥保存加密算法足够强,密钥派生算法正规,你不能忘记助记词,等等等。

脱离安全假设来谈安全都是在耍流氓。一切安全都有前提的。只有经过数学证明之后,大家才能够确信这个 算法/方案 的安全性基于一些非常明确的「安全假设」。

在证明之前,还缺少一个东西,那就是「安全定义」。在多数人的认知系统中,安全就是一个框,什么都可以往里装。大家应该好好提醒下自己,当谈论安全二字的时候,有没有想过到底什么是安全?怎么算安全?

「安全」需要有一个数学意义上的严格定义

伟大的科学家香农(Claude Shannon)从信息论的角度给出了一个非常靠谱的安全性定义[2]:

完美安全:假设你是一个攻击者,你通过密文获取不到任何有价值的信息,破解的唯一手段就是靠瞎蒙。

大家想一想,这个定义很有趣,通过密文获取不到信息,这就意味着你没有获得任何额外的计算能力,能够帮助让你以更短的时间来计算出明文。

但是这个定义太完美,以至于使用的加密算法都很难满足这个安全性定义。后来 Goldwasser 与 Micali 等人写了另一篇载入史册的经典『概率加密』。

在这篇论文中定义了这样一个概念:语义安全。所谓语义安全在完美安全的定义上放松了些要求。

语义安全:假设你是一个攻击者,你通过密文在多项式时间内计算不出来任何有价值的信息。

好了,这个看起来靠谱多了。接下来一个问题就是,怎么理解「计算不出来信息」这个概念?这看来要对信息进行度量,信息的定义又是什么呢?

我们又引入一个概念——「不可区分性」,来重新表述加密算法的安全性:假设你是一个攻击者,而我有一个加密算法:

  1. 你随机产生两段等长的明文,m1=「白日依山尽,黄河入海流」,m2=「烫烫烫烫烫,烫烫烫烫烫」
  2. 你把这两段明文,m1m2 交给我
  3. 我随机挑选一个明文,不告诉你是哪一个,然后进行加密,产生一个密文 c
  4. 我把密文 c 出示给你看,让你猜这个 c 究竟是由唐诗加密产生,还是乱码加密产生
  5. 如果你用一台计算机来破解 c,在多项式时间内破解不出来,也就是说你没办法区分 c 的来源,那么就说明加密算法是语义安全的

OK,理解完「不可区分性」,我们再回到「零知识」,如何证明一个交互式系统是「零知识」呢?首先我们要定义下零知识这个概念。

注:不可区分性是概率意义上的不可区分;在学术上,它可以分为「完全不可区分」,「统计不可区分」,还有「计算不可区分」。在本文中,我们暂时不需要理解这些概念的差别。

模拟器

设想在平行宇宙中,有两个平行的世界,一个叫做「理想世界」(Ideal World),另一个叫做「现实世界」(Real World)。我们每一个个体可以在两个平行世界中愉快地玩耍,但是两个世界的普通人无法互相感知,也无法互相沟通。

假设「你」是一个很厉害的密码破解者,而且「你」不是普通人,具备在平行宇宙之间穿梭的能力。而 Alice 有一个地图三染色的答案,你的目的是通过和 Alice 对话来获取地图三染色的答案,会话的过程参考上一篇文章的「地图三染色问题」协议。

继续脑洞,Alice 只存在「现实世界」中;在「理想世界」,Alice 被「替换」成了一个长相与声音一模一样的个体,我们称替身为 Zlice。下一步,把「你」同时放入两个世界中,但不让你知道是你当前位于哪一个世界。你的两个分身所面对的都是一个 “Alice”模样的人。

再重复一遍,在「现实世界」中, 与你对话的是一个真实的,并且诚实的 Alice;而在「理想世界」中,与你对话的是 Zlice (假 Alice),Zlice 虽然相貌语言与 Alice 并无二致,但差异是,Zlice 并不知道「知识」,即不知道一个三染色问题的答案。

接下来在这两个世界中,你的两个分身将同时与真假 Alice 进行对话。神奇的事情发生了,最终在两个世界中,你的两个分身都被说服了,都经过 n 轮挑战,没有发现对方作弊,即「你」的两个分身都认为对方确实知道「答案」。换句话说,「你」没有能力「区分」出来自己到底在 「现实世界」 还是 「理想世界」,当然也没能力「区分」和自己对话的究竟是 Alice 还是 Zlice。不仅如此,对于吃瓜群众我而言,如果把「我」作为观察者放入任何一个世界中,我会和你一样「无法区分」出来眼前的 这个长相为 “Alice” 的人到底是真还是假。

下面是烧脑结论:

这个交互系统为何是「零知识」?因为 Zlice 是没有任何知识,而且她和 Alice 不可区分。

我再换个方式解释:因为你和我都没办法区分我们究竟是在哪个世界中,两个世界发生的交互过程几乎不可区分,而且其中一个世界中根本就不存在知识,因此,我们说这个交互协议——「地图三染色问题」是「零知识的」。

这里还有个前提,理想世界 必须是算法可构造的。然后,有一个「神」,他通过算法「模拟」了一个「理想世界」,其中构造了一个算法叫做 Zlice,她没有「知识」作为输入,也即「零知识」;除此之外,「理想世界」与「现实世界」一模一样。

设想你在对话过程中,如果真 Alice 泄露了信息,那么你就能立即区分出面前这个人是 真 Alice 还是 Zlice,Zlice 是不可能伪装泄露信息的。因此可以得出结论:

真 Alice 没有泄露任何信息。

这个神,被称为「模拟器」(Simulator),而在理想世界中,和你对话的这个 Zlice 幻象其实也是「模拟器」,你在理想世界中,所有能感知到的东西都是模拟器「模拟」出来的。

好了,到这里,我们用「模拟器」这个概念对「零知识」进行了定义。