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

I know that I know nothing —— 苏格拉底
相信很多人都听说过零知识证明，但是只有极少数人听说过模拟，然而模拟是理解零知识的关键。
我们在第一篇文章『初识「零知识」与「证明」』（链接）[1]中介绍了一个简单的零知识交互系统：地图三染色问题。那么这个系统真的是零知识的吗？我们为什么要相信这个结论呢？有证明吗？在 Alice 与 Bob 的对话过程中，如果不零知识， Alice就被坑了。交互式系统的设计者「我」需要让 Alice 确信，这个对话确实是零知识的。
如果从直觉主义角度解释，要证明一个交互系统中存在信息泄露，那么你只需要指证：第几个 bit 导致信息泄露即可；但如果要证明不存在信息泄露，那么你要对着所有信息流中的所有 bit 说，这从1 ， 2 ， 3 ， 4 ， 5 ， …… 编号的 bit 都没泄露任何信息。看官们，这是不是很难？
本文约八千字，略微烧脑。
安全的定义与不可区分性
首先，一个交互式系统，也就是一个对话，它的「零知识」需要证明。毕竟，现代密码学是建立在严格的形式化系统之上。在证明之前，还需要明确「安全假设」到底有哪些。所谓安全假设，比如我们说一个系统的权限隔离做得无比精确，每一个用户只能看到被授权的信息，但是这基于一个安全假设：管理员账号没有被破解。又比如在手机银行软件里，只能通过短信认证码，才能完成转账功能，这也基于一个安全假设：你的手机 SIM 卡没有被克隆。如果我们深入地分析每一个我们感觉安全的系统，都存在大量的似乎不那么稳固的安全假设。比特币私钥安全吗？比特币账户的安全假设也不少：首先你的助记词不能让别人知道，手机钱包里私钥保存加密算法足够强，密钥派生算法正规，你不能忘记助记词，等等等。
脱离安全假设来谈安全都是在耍流氓。一切安全都有前提的。只有经过数学证明之后，大家才能够确信这个算法/方案的安全性基于一些非常明确的「安全假设」。
在证明之前，还缺少一个东西，那就是「安全定义」。在多数人的认知系统中，安全就是一个框，什么都可以往里装。大家应该好好提醒下自己，当谈论安全二字的时候，有没有想过到底什么是安全？怎么算安全？
「安全」需要有一个数学意义上的严格定义
伟大的科学家香农（Claude Shannon）从信息论的角度给出了一个非常靠谱的安全性定义[2]：
完美安全：假设你是一个攻击者，你通过密文获取不到任何有价值的信息，破解的唯一手段就是靠瞎蒙。
大家想一想，这个定义很有趣，通过密文获取不到信息，这就意味着你没有获得任何额外的计算能力，能够帮助让你以更短的时间来计算出明文。
但是这个定义太完美，以至于使用的加密算法都很难满足这个安全性定义。后来 Goldwasser 与 Micali 等人写了另一篇载入史册的经典『概率加密』[2] 。
在这篇论文中定义了这样一个概念：语义安全。所谓语义安全在完美安全的定义上放松了些要求。
语义安全：假设你是一个攻击者，你通过密文在多项式时间内计算不出来任何有价值的信息。

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

猜你喜欢

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