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

研究前沿密码 (同态加密、安全多方计算等) 的密码人

参考自 Ivan Damgård BRICS (Århus University) 的主题演讲，Ivan Damgård是丹麦著名的密码学家，SPDZ协议的主要开创者。这应该是20年前的一次演讲文稿，但可以从中学习一些思想。有兴趣的朋友可以读一下。

作者：六三

日期：2021年4月

摘要：本篇文章带来的是MPC的入门级介绍。

零、写在前面

我们的OpenMPC(开放隐私计算)社群已初具规模, 如有想加入我们的小伙伴, 可以私信我或OpenMPC的创始人@开放隐私计算，我们拉您进群。

如果心揣梦想, 想更在这个领域进一步做点事情, 那么请联系我们, 我们将会热烈欢迎您成为我们的一份子。

一、MPC problem

1.1 前提与目标

前提：

假设有 n 个参与方 P_1,P_2,...,P_n 。 P_i 持有输入 x_i 。

目标：

对于一些有 n 个输入和 n 个输出的给定函数 f ，安全地计算 f(x_1,...,x_n)=(y_1,...,y_n) ，也就是说，我们想要一个这样的协议：

P_i 学习 y_i 的正确值
除了从 x_i 和 y_i 中得到的信息外，没有任何关于输入的信息被泄露给 P_i 。

我们希望以上能够保持，甚至当（部分）参与方的行为是对抗性的。

1.2 例子

姚院士的百万富翁问题

两个百万富翁 A、B 在街上相遇，他们能否在不透露任何进一步信息的情况下比较谁更富有。我们对以上问题形式化表示：

计算安全函数 f(x,y) ，接受输入整数 x,y ，如果 x>y 有 x 百万，结果是1，他知道 B 的钱少于 x 百万，但他不应该进一步了解任何信息。

问题：假设参与方都遵循指令，函数 f(x,y)=x+y 很容易安全计算。你会怎么做？如果参与方可能偏离协议，你的解决方案还能用吗？

带着疑问我们往下看

1.3 通用性

MPC具有足够通用性: 一个解决方案原则上意味着任何加密协议问题的解决方案。但请注意，并非所有问题都可以通过安全计算单个函数来建模。例如，安全电子支付，它更像是几个函数的安全计算，跟踪之间的一些状态信息。

然而，这不是一个问题，我们将看到的定义是完全通用的，我们描述的协议实际上也是完全通用的，尽管为了简单起见，它们被称为计算单个函数的解决方案。

1.4 建模对抗行为

假设一个敌手 \mathcal {ADV} 。

\mathcal {ADV} 可能会腐蚀一些参与方并使用它来学习他不应该知道的信息，或者破坏结果。当 P_i 被腐蚀时， \mathcal {ADV} 学习 P_i 的完整历史记录。

\mathcal {ADV} 按照属性可分类为：

被动或主动: 只需监控腐坏的参与方，或者对其进行完全控制。
静态或自适应: 所有腐蚀都发生在协议启动之前，或者在协议期间动态发生。
无界限或概率多项式时间。

通过对抗行为的描述，我们将得到一个更精确的 MPC 目标：希望协议工作时，就好像我们有一个值得信赖的一方 T ，它从参与方那里获取输入，计算结果并将其返回给参与方一样，因此， \mathcal {ADV} 可以决定腐坏参与方的输入，但诚实的参与方可以获得正确的结果，协议只告诉 \mathcal {ADV} 被腐蚀参与方的输入/输出。

1.5 腐坏的界限

如果 \mathcal {ADV} 可以破坏参与方的任意子集，那么在大多数情况下问题无法解决，例如，如果每个参与方都被腐蚀，那么何谈安全性呢？

因此需要定义一些可以腐坏子集的界限：

敌手结构 \Gamma : P=\{P_1,…,P_n\} 的子集族， \mathcal {ADV} 是一个 \Gamma -adversary，一组腐坏的参与方在所有时间都在 \Gamma 。

为了使之合理， \Gamma 必须是单调的。 B\in Γ 和 A\subseteq B 意味着 A\in Γ 也就是说，如果 \mathcal {ADV} 可以破坏集合 B ，他可以选择破坏任何较小的集合。

Threshold-T 结构: 包含最多 T 大小的所有子集。

Γ 为 Q3 ：对于任意 A_1,A_2,A_3\in Γ ， A_1\cup A_2\cup A_3 小于 P 。

Γ 为 Q2 ：对于任意 A_1,A_2\in Γ ， A_1\cup A_2 小于 P 。

t<n/3 的 Threshold-T 结构为 Q3 。

t<n/2 的 Threshold-T 结构为 Q2 。

为什么使用以上通用访问结构，而不仅仅是可以腐坏的参与方数量？

门限敌手 (我们只是约束了腐坏的数量) 在一个所有节点都同样难以侵入的网络中是有意义的。但实际情况往往不是这样。

通过一般的访问结构，我们可以表达这样的意思：敌手可以突破少量的比较安全的节点和大量的不太安全的节点。

1.6 建模通信

异步网络，即敌手看到所有消息，可以无限期地延迟它们。在这种网络上，某些形式的 MP C问题更难或不可能，在任何情况下都会产生额外的复杂性。

同步网络，通信分回合进行，在每轮中，每个参与方都可以向彼此发送消息，所有消息都是在同一轮中接收的。

两个主要变体:

信息论场景. \mathcal {ADV} 没有看到诚实（未腐坏）参与方之间的通信，即可以获得不受限制的 \mathcal {ADV} 的安全性。
加密场景。 \mathcal {ADV} 可以看到所有发送的信息，但不能改变诚实玩家之间的信息交换，即只能获得（多项式时间）约束的 \mathcal {ADV} 的安全性。