安全多方计算入门级介绍二

陆叁 2021-09-25

636

点击上方蓝字获取更多新鲜资讯

一、定义MPC的安全性

方法：定义我们想要的理想版本。如果它 "相当于” 理想说明协议是好的。

优点：从等效性来看，我们知道协议具有理想版本的所有良好属性。

我们将为通用可组合(UC)安全性提供 Canetti 定义的变体。(变体主要区别: 明确考虑同步网络，原始UC用于异步情况)。

1.1 敌手活动

定义前的重要说明：一般情况下，敌手可能会比腐蚀参与方和控制他们的行为更有能力。- 大多数协议都是作为一个更大的系统的一部分来运行的，比如密钥交换协议或电子支付方案。- 现实生活中的敌手会攻击整个系统，而不仅仅是协议。- 因此，敌手可能会对诚实的参与方所提供的输入产生一定的影响，甚至可能控制它们。- 另外，敌手可能会得到一些关于诚实参与方从协议中获得的结果的信息，甚至可能是全部信息。

在我们的定义中，敌手应该被允许为诚实参与方选择输入，并看到他们的结果。

问题：这是非常奇怪的，我们不是说过，敌手不应该得到诚实玩家的结果信息吗？

回答：我们说的是协议不应该发布这种信息。如果敌手从其他渠道，比如周围的系统了解到一些信息，协议也无能为力。所以我们要要求协议按照它应该的方式工作，不管敌手知道什么，或者能通过协议外部的手段控制什么。

1.2 定义中的概念

所有的实体（参与方、敌手、可信方）从形式上讲都是交互式的、概率的图灵机。每个实体都得到作为输入的安全参数，得到辅助输入。

理想范式（或可信方）。

模拟我们希望协议实现的范式。
不能被腐蚀
可以与所有参与方和敌手进行交流。
接收来自所有参与方的输入，根据其程序进行计算并将结果返回给参与方。
有内存，可以多次调用，因此可以用来模拟我们能想象到的任何合理的基元。

当然，现实生活中不存在这样的，只是用了一个我们希望拥有的规范。定义基本上说，如果一个协议在现实生活中创造了相当于有可用的情况，那么这个协议就是好的（w.r.t. ）。

定义两个过程。- 真实过程 - 理想过程

在真实过程中，我们有敌手和执行协议的参与方（没有可信方）。

在理想过程中，我们仍然有，但被可信方（加上后面要解释的模拟器）代替。

如果无法判断自己是在真实过程中还是在理想过程中，我们将说安全地实现了。

下面图中显示了真实过程。

下面图中显示了理想过程。

为了让在真实中的事情和理想过程中的事情看起来是一样的，我们引入模拟器。

1.3 定义

我们说，如果存在一个模拟器，使得对于所有的敌手只在中腐坏集合，并满足：

则安全地完美地实现了。

Intuition：我们认为的输出是它对自己是在现实世界还是理想世界的猜测。两个概率相等意味着它无法分辨。注意我们说的是对所有而言，所以这里没有对的计算能力进行约束。

如果以下计算成立，则说明实现了统计上的：

其中，表示在中的可忽略值（对于任意选择）。

Intuition on Definition

它确保现实过程继承了理想过程的自然安全属性，例如：

协议确保诚实的参与方计算出正确的结果：在理想过程中，通过对的定义，总是真实的，如果协议产生不一致的结果，可以很容易地区分。
协议不释放不该释放的信息：能够令人信服地模拟攻击协议的观点，只根据愿意透露给腐坏参与方的内容。

问题：考虑计算的 trivial 协议，显示它满足定义（假设为被动腐坏）。假设我们尝试用同样的 trivial 方案来计算两个比特的AND。解释为什么在这种情况下证明会失败。

Secret Sharing

Dealer 在中持有一个秘密值，

Dealer 在上选择一个阶最多为的随机多项式，使得。

Dealer 私下发送至。

Properties:

任何最多个参与方的子集都没有的信息。
任何至少个玩家的子集都可以很容易地计算出，可以通过取他们所知道的 share 的线性组合来完成。

为了便于理解，我将shamir算法贴在这里
shamir是一种秘密共享的实现，利用了拉格朗日插值公式。详细原理见参考文献。下面补充一个shamir算法的有用的性质: 加同态。已知已有两个用于秘密共享的多项式
以及素数 . 通过秘密共享分享的分片形式是。将分片中的多项式结果求和，得到。根据shamir算法中的定义，是原秘密。因此通过恢复算法对求和后的分片进行恢复，将会得到。这就实现了秘密求和。在双方求和的情况下，没有意义，但在参与者数目大于等于3时，就会有用。
拉格朗日插值：blog.csdn.net/shenwansa