Simulation-Based Security

1. 背景介绍
2. 实例：地图 3 染色问题
- 2.1. 交互协议
- 2.2. 证明
3. 实例：Schnorr's Protocol
4. 参考

1. 背景介绍

在零知识证明、多方安全计算等场景中，协议的参与者往往需要确保自己的某个秘密不能以某种形式泄露给对方。问题来了，我们如何证明协议是安全的，参与者确实没有以某种形式泄露秘密呢？

本文介绍的“Simulation-Based Security”就是干这个事的。其证明思路如下：

首先「零知识」是为了保护 Alice 的利益，因为 Alice 不想在交互过程中透露更多的信息给 Bob，不想让 Bob 知道她所拥有的秘密 w，甚至不想让 Bob 从交互的过程中分析出哪怕一丁点的信息。那么怎么保证这一点呢？「模拟器」这时候登场了，它能模拟出一个和现实世界外表一模一样的「理想世界」，然后「模拟器」在这个世界中可以轻松地骗过任何一个对手，让对方无法分辨自己是在现实世界中，还是理想世界中。因为「模拟器」手里没有那个秘密 w，「理想世界」是零知识的。又因为两个世界的不可区分性，所以我们可以得出结论：Alice 的交互协议是「零知识」的。

摘自：https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/2/zkp-simu.md

在“Ideal World”中，模拟器没有原始秘密值，如果能找到一种方式“骗过”所有对手，让对手分不清“Real World”和“Ideal World”，则称协议满足“Simulation-Based Security”。如图 1 所示。

Figure 1: Simulation Paradigm（“Ideal World”中模拟器接管了交互过程）

既然模拟器没有原始秘密值，那它如何能“骗过”所有对手呢？关键在于模拟器有超能力：它可以“回到过去”（Rewind）。

2. 实例：地图 3 染色问题

地图 3 染色问题是个经典问题：如何用 3 种颜色对一个地图进行染色，保证任意两个相邻的地区都是不同的颜色。这个问题可以转换为“连通图的顶点三染色问题”：如何对连通图染色，使其每个边的两个顶点的颜色都不同。

现在，假设 Alice 知道了问题的解，Alice 想向 Bob 证明她知道问题的解，但同时 Alice 不想把算法告诉 Bob。这应该怎样实现呢？

2.1. 交互协议

利用图 2（摘自 https://eprint.iacr.org/2016/046 ）所示的交互协议，Prover 在不泄露解的条件下，可以向 Verifier 证明他知道解。

Figure 2: Zero-Knowledge Proof for 3-Coloring

图 2 所示协议看起来比较晦涩，下面用朴实的语言进行描述，摘自 https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/1/zkp-back.md 。

第一步，Alice 把她的答案加密，且每一个顶点都用纸片盖上，Bob 无法打开。如图 3 所示。

Figure 3: Commit

第二步，Bob 随机挑选一条边，要 Alice 打开。如图 4 所示。

Figure 4: Challenge

第三步，Alice 打开 Bob 要求查看的那条边给 Bob 验证。如图 5 所示。

Figure 5: Response

当然，上面过程要重复很多次，这样如果 Alice 没有答案，她无法每次蒙对。

2.2. 证明

如何证明前面的协议中，Prover（Alice）确实没有泄露问题的解呢？如果采用“Simulation-Based Security”，则只需要证明存在一种模拟器算法可以让“Ideal World”和“Real World”无法区分即可。

事实上，这种模拟器算法是存在的，如图 6（摘自 https://eprint.iacr.org/2016/046 ）所示。

Figure 6: Simulation-Based Security

图 6 所示过程看起来比较晦涩，下面用朴实的语言进行描述，摘自 https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/2/zkp-simu.md

在“Ideal World”中，跟 Bob 对话的是一个“Simulator”，它模拟出了整个世界的样子。Bob 按照 3 染色问题的交互协议进行交互。模拟器并没有一个 3 染色答案，它索性把所有的顶点都染成了灰色。

首先，模拟器模仿 Alice ，把每个顶点用纸片盖起来。然后发给 Bob。如图 7 所示。

Figure 7: 模拟器模仿 Alice ，把每个顶点用纸片盖起来

Bob 随机挑选了一条边，挑战证明者。如图 8 所示。

Figure 8: Bob 随机挑选了一条边，挑战证明者

模拟器这时候不能打开纸片，因为这条边两端的颜色都是灰色的，无法通过验证。如图 9 所示。

Figure 9: 模拟器这时候不能打开纸片

这时候，模拟器要发挥“超能力”了，他运用时间倒流（Rewind）的技能，回到对话第一步之前。如图 10 所示。

Figure 10: 运用时间倒流（Rewind）的技能，回到对话第一步之前

模拟器现在处于第一步，他把最下面那条边的两端染上任意不同的颜色，然后重新盖上纸片，并发给 Bob。如图 11 所示。

Figure 11: 模拟器把最下面那条边的两端染上任意不同的颜色

Bob 这时候无法感知到时间已经倒退回第一步了，对他来说，一切都是新鲜的，他“诚实”地再次选择了最下面的边。如图 12 所示。

Figure 12: Bob 再次选择了最下面的边

这时候模拟器就可以放心地打开纸片，让 Bob 检查。Bob 很显然会被骗过。如图 13 所示。

Figure 13: 模拟器就可以放心地打开纸片，让 Bob 检查

然后 Bob 一轮轮地重复这个过程，每一次模拟器都能用时间倒流的方式骗过 Bob。

从而，尽管模拟器没有 3 染色问题的解，但它也可以在“Ideal World”中骗过 Bob，从而前面介绍的协议具有“Simulation-Based Security”。

3. 实例：Schnorr's Protocol

利用 Schnorr 协议（如图 14 右子图所示，摘自 https://www.youtube.com/watch?t=480&v=_YpGx_nLJow ）可以在不泄露私钥的情况下，向别人证明自己提供的数据是私钥所对应的公钥。

我们可以找到一个模拟器算法（如图 14 左子图所示），可以欺骗 Verifier，从而 Schnorr 协议是零知识协议。

Figure 14: 模拟器算法（左），Schnorr 协议（右）

在模拟器算法中，由于模拟器没有私钥 $w$ ，所以无法像 Schnorr 协议一样使用 $z = r + e w$ 来计算 $z$ ，模拟器随机产生 $z$ 即可。由于模拟器具备 Rewind 的能力，所以模拟器在收到 Verifier 的 $e$ 值后，再回退到第一步中按 $A = g^{z} \cdot h^{- e}$ 计算 $A$ 即可骗过 Verifier。

4. 参考

How To Simulate It - A Tutorial on the Simulation Proof Technique
A Pragmatic Introduction to Secure Multi-Party Computation, 2.3.1 Real-Ideal Paradigm
https://en.wikipedia.org/wiki/Secure_multi-party_computation#Security_definitions
https://www.youtube.com/watch?v=_YpGx_nLJow
https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/1/zkp-back.md
https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/2/zkp-simu.md