论Game-based Proof与Simulation-based Proof的区别

生活真是一地鸡毛，现在我身上还有好多清理不掉的毛渣渣——哎~

在《密史》里，我们作者挖坑留下了有关game-based proof和simulation-based proof的区别。经过了这一年的思考和沉淀，我们向前走了一步，有了更深的理解。

• Game-Based Proof：通过和敌人玩预定的游戏提供信息，证明方案的安全性。主要用于方案的证明

• Simulation-Based Proof：通过向敌人模拟它想要的信息，证明协议的安全性。主要用于协议的证明

上述的区别会被揍的。所以，我们有了以下的新理解。

背景知识：

敌人初始化知道了信息A。

敌人通过另外渠道获得了信息B。

问题1： 敌人能否通过A+B 计算出之外的信息，记为C呢？ 这个问题在方案里很常见。比如，敌人获取了A（公钥），然后通过询问获取了B（签名之类的信息）。从安全的角度，我们希望敌人不能计算出A+B之外的信息C（对某新消息的签名）。

问题2：敌人能否通过B获取A之外的信息，记为C呢？这个问题在协议里很常见。比如，敌人获取了A（1-out-of-2 OT不经意传输协议里该知道的公钥以及它最终选择得到的消息m_1），然后获取了B(发送方和敌人通讯过程所有的传输，可以理解为包含了m_0和m_1的通讯内容)。从安全的角度，我们希望敌人不能通过B炸出A之外的信息C（比如又获取了m_0）。

为了解决问题1，密史发明了game-based proof。 假如存在一个困难问题（比如已知g和g^x,计算x）， 那么我们通过g和g^x来模拟A+B。 如果敌人能够计算C且我们能通过C抽取出x， 那么说明了 敌人计算出C 是不可能的，即该方案是安全的。

为了解决问题2，密史发明了simulation-based proof。假如我们能够通过A来模拟B，那么敌人一定不能从B获取出A之外的信息C。注意了，这里的信息C指的是从A获取不了的信息。

所以，game-based proof是一种“证明存在知识差”的技巧（因为知道[g,g^x]和知道[g,g^x,x]是不一样的），而simulation-based proof是一种“证明没有知识差”的技巧（因为知道A和知道B是一样的）。

然后呢？ 尝试把这两种证明对立起来应该会很痛苦的。

• 首先，game-based proof里，A+B都是通过从困难问题的instance进行simulation得来的，所以，有simulation-based proof里simulation的影子。

• 其次，simulation-based proof里，当我们证明A可以模拟B达到不可区分时，我们是这么干的：假如他们可以区分，那么我们就归约解决某个难题。这一步属于game-based proof。

最后，给两个例子解释什么是协议里的A和B。

第一个例子： 在ZKP里，A是statement, 比如[g,g^x],  而B是一次的交互式证明包含了[承诺，挑战，回应]。 我们通过A来模拟B,从而说明证明不会泄露A之外的秘密knowledge, 达到零泄漏。

第二个例子：在MPC里，A是敌人在理想世界获得的信息，而B是敌人在真实世界获得的信息以及协议通讯过程的一切通讯内容（当然了，被加密保护的）。我们通过A来模拟B，如果可以模拟，那说明敌人是在真实世界掀不起大浪的。

问：那我们要采取哪个方式证明我设计的方案或协议呢？

答：天知地知，但我不知。要不，你从安全需求（问题1和问题2）着手

========================我是抛砖引玉专用线===========================

                                 请大胆留言，帮忙把密史的这个坑填起来。