安全多方计算定义

符号和惯用表示

安全多方计算（Secure Multy-Party Computation，SMC）

缩写为 MPC，用于表示两个或多个参与方之间的安全计算过程

安全函数求值（Secure Function Evaluation， SFE）

缩写为 SFE，含义与 SMC 基本相同，在特定场景下 SFE 可以用于表示“仅有一个参与方提供私有输入，由外包服务器计算函数输出”的安全计算过程

只有两方参与的安全多方计算

由于两方 MPC 是一个重要的特例，已经对其做了大量针对性研究，所以有时用 2PC 来强调只考虑两方 MPC

加密解密

使用 $ Enc_{k}(m) $ 来表示用密钥 $ k $ 加密消息 $ m $，使用 $ Dec_{k}(m) $ 来表示用密钥 $ k $ 解密消息 $ m $

可忽略函数

可忽略函数 $ \upsilon : \mathbb{N} \rightarrow \mathbb{R} $ 是一个趋近于 0 的速度比任何逆多项式都快的函数。对于任意多项式 $ p $，除了有限多个 $ n $ 外，均有 $ \upsilon(n) < \frac{1}{p(n)} $

安全参数

我们使用 $ \kappa(kappa) $ 来表示计算安全参数，使用 $ \sigma $ 来表示统计安全参数。计算安全参数 $ \kappa $ 表示攻击者应用离线计算破解一个问题的困难程度，如破解一个加密算法的困难程度。在实际中通常将 $ \kappa $ 设置为 128 或 256。统计安全参数 $ \sigma $ 表示攻击者实施此类攻击的困难程度。在实际中通常将 $ \sigma $ 设置为一个较小的值如 40 或 80.一种正确理解两个安全参数含义的方法是：协议仅有 $ 2^{-\sigma} + \upsilon(\kappa) $ 的概率不满足安全性。当考虑具有无穷计算能力的攻击者时忽略 $ \upsilon $ 并要求 $ \upsilon = 0 $

均匀随机采样

使用 $ \in_{R} $ 来表示从某一分布均匀随机地采样得到一个元素。如，使用“选择 $ k \in_{R} \{0, 1\}^{\kappa} $”表示 $ k $ 是均匀随机选取的 $ \kappa $ 比特长字符串。更一般的，使用 $ \upsilon \in_{R}D $ 来表示依某个概率分布 $ D $ 采样得到一个元素，使用 $ \upsilon \in_{R}A(x) $ 表示 $ \upsilon $ 是以 $ x $ 为输入执行随机性算法 $ A $ 后得到的输出。

不可区分性和统计距离

令 $ D_{1} $ 和 $ D_{2} $ 为两个以安全参数为索引的概率分布。另一种等价表述是：$ D_{1} $ 和 $ D_{2} $ 是以安全参数为输入的两个算法。如果对于所有的算法 $ A $，存在一个可忽略函数 $ \upsilon $，满足：$ Pr[A(D_{1}(n)) = 1] - Pr[A(D_{2}(n)) = 1] \leq \upsilon(n) $，则称 $ D_{1}$ 和 $ D_{2} $ 是不可区分的（Indistinguishable）。换句话说，当以根据 $ D_{1} $ 或 $ D_{2} $ 采样得到的样本做为输入时，任何一个算法 $ A $ 的执行差异都不会超过可忽略函数。如果仅靠了非均匀（Non-uniform）、多项式时间（Polynomial-time）算法 $ A $ ，则此定义描述的是计算不可区分性（Computational Indistinguishability）。如果考虑所有算法而不考虑算法的计算复杂性，则此定义描述的是统计不可区分性（Statistical Indistinguishability）。在后一种情况下两个概率分布的差异上界为两个概率分布的统计距离（Statistical Distance）（也称为总变差距离），定义为 $ \Delta(D_{1}(N), D_{2}(N)) = \frac{1}{2} \sum\limits_{x} | Pr[x = D_{1}(n)] - Pr[x = D_{2}(n)] | $。在之后使用计算安全行来表示非均匀多项式时间攻击者攻击下的安全性，用信息论安全性表示任意攻击者攻击下的安全性（攻击者可能拥有无限计算资源）

基础原语

秘密分享

详见Shamir门限秘密共享方案

随机语言机（Random Oracle，RO）

随机语言机是描述哈希函数安全性的一个启发式模型，它的基本思想是将哈希函数看作公开的理想随机函数。在随机语言机模型中，所有参与方都可以访问用状态语言机实现的公开函数 $ H: \{0, 1\}^{*} \rightarrow \{0, 1\}^{\kappa} $。给定输入字符串 $ x \in \{0, 1\}^{*} $，$ H $ 查找自身的调用记录，若之前从未调用过 $ H(x) $，则 $ H $ 随机选择 $ r_{x} \in \{0, 1\}^{\kappa} $，记录输入/输出对 $ (x, r_{x}) $，并返回 $ r_{x} $。如果之前调用过 $ H(x) $，则 $ H $ 返回 $ r_{x} $。预言机通过这种方式实现了一个随机选择函数 $ \{0, 1\}^{*} \rightarrow \{0, 1\}^{\kappa} $。

MPC 安全性

现实-理想范式

当定义安全性时，很自然的想法是列举一个“安全检查清单”，美剧出哪些情况属于违反安全性要求。这种安全性定义方式不仅非常繁琐，而且很容易出现错误，很难保证“安全检查清单”是否枚举出了所有安全性要求。
现实-理想范式避免采取上述的安全性要求描述方式，而是引入了一个定义明确、涵盖所有安全性要求的“理想世界”，通过论述现实世界与理想世界的关系来定义安全性。

理想世界
在理想世界中各个参与方秘密地将自己的私有输入发送给一个完全可信的参与方 $ \mathcal{T} $（一般称这个完全可信的参与方 $ \mathcal{T} $ 为一个功能函数），由后者来安全地计算函数 $ \mathcal{F} $，每个参与方 $ P_{i} $ 都拥有自己的私有输入 $ x_{i} $。各个参与方将私有输入发送给$ \mathcal{T} $，$ \mathcal{T} $ 只需要计算 $ \mathcal{F}(x_{1}, \dots, x_{n}) $，并将结果返回给所有参与方。通常我们称 $ \mathcal{F} $ 为可信参与方（功能函数），称 $ \mathcal{C} $ 为可信参与方在私有输入下的待运行电路。
当一个理想世界的攻击者在理想世界中发起攻击时，他可以控制任意一个或多个参与方 $ P_{i} $，但不能控制 $ \mathcal{T} $。考虑之前给出的“安全检查清单”：攻击者很明显无法得到除 $ \mathcal{F}(x_{1}, \dots, x_{n}) $ 之外的任何信息，因为攻击者只能接收到 $ \mathcal{F}(x_{1}, \dots, x_{n}) $；可信参与方发送给诚实参与方的输出都是一致、有效的；攻击者选择的输入与诚实参与方的输入是相互独立的。
现实世界
现实世界不存在可信参与方，所有参与方通过协议相互通信。协议 $ \pi $ 为每个参与方 $ P_{i} $ 指定“下一个消息”函数 $ \pi_{i} $。“下一个消息”函数的输入是安全参数、参与方的私有输入 $ x_{i} $、随机带以及 $ P_{i} $ 到目前为止收到的所有信息所构成的列表。随后，$ \pi_{i} $ 输出要发送到下一个目的地的“下一条消息”，或者指示该参与方给出某个特定的输出，表示中止协议。
在现实世界中，攻击者可以攻陷参与方。在协议开始执行之前就被攻陷的参与方与原始参与方就是攻击者是等价的。

直观地讲，如果攻击者实施攻击后，其在现实世界中达到的攻击效果与其在理想世界中达到的攻击效果相同，则可以认为现实世界中的协议是安全的。

半诚实安全性

概念请见：一些隐私计算的基础知识
使用形式化预言定义显示-理想范式。令 $ \pi $ 为一个协议，$ \mathcal{F} $ 为一个功能函数。令 $ \mathcal{C} $ 为攻陷参与方集合，令 $ Sim $ 为一个仿真者算法。定义下述两个随机变量的概率分布：

$ Real_{\pi}(\kappa, \mathcal{C};x_{1}, \dots, x_{n}) $：在安全参数 $ \kappa $ 下执行协议，其中每个参与方 $ P_{i} $ 都将使用自己的私有输入 $ x_{i} $ 诚实地执行协议。令 $ V_{i} $ 为参与方 $ P_{i} $ 的最终视角，令 $ y_{i} $ 为参与方 $ P_{i} $ 的最终输出。
$ Ideal_{\mathcal(F), Sim}(\kappa, \mathcal{C};x_{1}, \dots, x_{n}) $：计算 $ (y_{1}, \dots, y_{n}) \leftarrow \mathcal{F}(x_{1}, \dots, x_{n}) $。输出 $ Sim(\mathcal{C}, \{(x_{i}, y_{i})|i \in \mathcal{C} \}) $

如果现实世界中攻陷参与方所拥有的视角与理想世界中攻击者所拥有的视角不可区分，则协议在半诚实攻击者的攻击下是安全的，即有如下定义：

给定协议 $ \pi $，如果存在一个仿真者 $ Sim $，使得对于攻陷参与方集合 $ \mathcal{C} $ 的所有子集，对于所有的输入 $ x_{1}, \dots, x_{n} $，概率分布 $ Real_{\pi}(\kappa, \mathcal{C};x_{1}, \dots, x_{n}) $ 和 $ Ideal_{\mathcal(F), Sim}(\kappa, \mathcal{C};x_{1}, \dots, x_{n}) $ 在 $ \kappa $ 下是不可区分的，则称此协议 在半诚实攻击者存在的条件下安全地实现了 $ \mathcal{F} $

恶意安全性

概念请见：一些隐私计算的基础知识

在通过现实和理想世界的差异来对协议安全性进行定义时要考虑的两个重要的附加因素：

攻陷参与方偏离协议规则执行协议可能会对诚实参与方的输出造成影响
在现实世界中无法定义恶意参与方的输入，所以我们让仿真者选择攻陷参与方的输入，而这个仿真过程称为输入提取

当用 $ \mathcal{A} $ 表示攻击程序时，我们用 $ corrupt(\mathcal(A)) $ 表示被现实世界中的攻击者 $ \mathcal{A} $ 攻陷的参与方集合，用$ corrupt(Sim) $ 表示被理想世界中的攻击者 $ Sim $ 攻陷的参与方集合，与半诚实安全性协议相同，我们定义现实和理想世界的概率分布，并定义一个安全协议使这两个概率分布满足不可区分性：

$ Real_{\pi, \mathcal{A}}(\kappa;\{x_{i} | i \notin corrupt(\mathcal(A))\}) $：在安全参数 $ \kappa $ 下执行协议，其中每个诚实参与方 $ P_{i} $（所有的 $ i \notin corrupt(\mathcal{A}) $）使用给定的私有输入 $ x_{i} $ 诚实地执行协议，而攻陷参与方的信息将由 $ \mathcal{A} $ 选取（将 $ \mathcal{A} $ 看作被攻陷参与方的“下一条消息”函数）。令 $ y_{i} $ 表示每个诚实参与方 $ P_{i} $ 的输出，令 $ V_{i} $ 表示参与方 $ P_{i} $ 的最终视角。输出 $ (\{V_{i} | i \in corrupt(\mathcal{A})\}, \{y_{i} | i \notin corrupt(\mathcal{A})\}) $。
$ Ideal_{\mathcal{F}, Sim}(\kappa; \{x_{i} \notin corrupt(\mathcal{A})\}) $：执行 $ Sim $，直至其输出一个输入集合 $ \{x_{i} \ i \in corrupt(\mathcal{A})\} $。计算 $ (y_{1}, \dots, y_{n}) \leftarrow \mathcal{F}(x_{1}, \dots, x_{n}) $。随后，将 $ \{y_{i} | i \in corrupt(\mathcal{A})\} $ 发送给 $ Sim $。令 $ V^{*} $ 表示 $ Sim $ 的最终输出（参与方的仿真视角集合）。输出 $ (V^{*}, \{y_{i} | \notin corrupta(Sim)\}) $。

给定协议 $ \pi $，如果任意一个现实世界中的攻击者 $ \mathcal{A} $，存在一个满足 $ corrupt(\mathcal{A}) = corrupt(Sim) $ 的仿真者 $ Sim $，使得对于城市参与方的所有输入$ \{x_{i} | i \notin corrupt(\mathcal{A})\} $，概率分布 $ Real_{\pi, \mathcal{A}}(\kappa;\{x_{i} | i \notin corrupt(\mathcal(A))\}) $ 和 $ Ideal_{\mathcal{F}, Sim}(\kappa; \{x_{i} \notin corrupt(\mathcal{A})\}) $ 在 $ \kappa $ 下是不可区分的，则称此协议 在恶意攻击者存在的条件下安全地实现了 $ \mathcal{F} $

交互功能函数

在理想世界中，功能函数仅包括一轮交互过程：提供输入，给出输出。可以进一步拓展 $ \mathcal{F} $ 的行为方式，令 $ \mathcal{F} $ 与参与方进行多轮交互，且在多轮交互过程中保持其内部状态的私有性。称此类功能函数为交互功能函数（Reactive Functionality）

可中止安全性

在所有基于消息的 2PC 协议中，一个参与方会在另一个参与方之前得到最终的输出，如果此参与方是恶意的攻陷参与方，它可以简单地拒绝将最后一条消息发送给诚实参与方，从而阻止诚实参与方得到输出。然而这种攻击行为与理想世界攻击行为不兼容。在理想世界中如果攻陷参与方可以从功能函数中得到输出，则所有参与方均可以得到输出。此性质称为输出公平性（Output Fairness）。并非所有的功能函数在计算过程中都可以满足输出公平性。
所以为了在恶意攻击场景下覆盖此攻击行为，提出了一种稍弱的安全性定义称为可中止安全性（Security with Abort）。在此定义中功能函数可以得知攻陷参与方的身份，在功能函数计算输出结果后，只将结果交付给攻陷参与方，并等待攻陷参与方的“交付”或“中止”，若收到“交付”命令则将结果发送给诚实参与方，若收到“中止”命令则向诚实参与方发送一个表示协议中止的输出（$ /perp $）。注意诚实参与方是否中止协议只能依赖于攻陷参与方的命令，如果概率依赖于诚实参与方的输入则该协议可能是不安全的。

适应性攻陷

在之前定义的现实世界和理想世界中，攻陷参与方在整个交互过程中都是不变的，我们称满足这一安全模型的协议在静态性攻陷（Static Corruption）下是安全的。可以考虑另一个场景，攻击者在协议执行期间根据交互过程中得到的信息决定攻陷哪些参与方，这一攻击行为称为适应性攻陷（Adaptive Corruption）。

可以在现实-理想范式中为适应性攻陷攻击行为建立安全模型，方法是允许攻击者发出形式为“攻陷 $ P_{i} $”的命令。在现实世界中这会使攻击者得到 $ P_{i} $ 的当前视角（包括 $ P_{i} $ 的内部私有随机状态），并接管其在协议执行过程中发送消息的控制权。在理想世界中，仿真者只能得到攻陷此参与方时该参与方的输入和输出，必须使用这些信息生成仿真视角。显然各个参与方的视角是相互关联的（若 $ P_{i} $ 向 $ P_{j} $ 发送一条消息，则此消息会同时包含在两个参与方的视角中）。适应性安全的挑战是仿真者必须住段生成攻陷参与方的视角。

混合世界与组合性

处于模块化考虑，设计协议时经常会让协议调用其他的理想功能函数。例如我们设计了一个安全实现某功能函数 $ \mathcal{F} $ 的协议 $ \pi $，同时还需要与另一个功能函数 $ \mathcal{G} $ 进行交互。该协议在现实世界中包含 $ \mathcal{G} $，但在理想世界仅包含 $ \mathcal{F} $。我们称这一修改后的现实世界为 $ \mathcal{G} $-混合世界

对安全模型的一个要求是组合性（Composition）：如果 $ \pi $ 是一个安全实现 $ \mathcal{F} $ 的 $ \mathcal{G} $-混合协议，且 $ \rho $ 是一个安全实现 $ \mathcal{G} $ 的协议，则以最直接的方式组合使用 $ \pi $ 和 $ \rho $ 应该可以得到安全实现 $ \mathcal{F} $ 的协议。一些非常直观的组合使用方式并不能保证多个安全协议可以安全组合，满足可组合性。

专用功能函数

不经意传输（OT），详见一些隐私计算的基础知识
承诺，详见同态承诺
零知识证明，详见零知识证明

参考文献

实用安全多方计算导论 /（美）戴维・埃文斯（David Evans），（美）弗拉基米尔・科列斯尼科夫（Vladimir Kolesnikov），（美）迈克・罗苏莱克（Mike Rosulek）著；刘巍然，丁晟超译。北京：机械工业出版社，2021.5