How To Simulate It – A Tutorial on the Simulation Proof Technique-Part3

Defining Security for Malicious Adversaries

Motivation

相比半诚实敌手下的安全性定义，恶意敌手会更难一些，因为恶意敌手可能会做出任何偏离协议规定的行为，只要求存在一个模拟器，能根据其规定的输入和输出生成被破坏方的视图就足够了。

但是，相较于之前的敌手，攻击者可能不使用给定的输入去输出，此外，除了要考虑到攻击者会从中获取额外的信息以外，还应当考虑到攻击者对于输出所带来的影响。

我们在分析协议的安全性时，会将对手在协议中能做的事情与在理想情况下能做的事情进行比较，而理想情况下的协议根据定义是安全的。此外，我们会设计一个不可篡改的可信第三方，各方将其输入发送给该第三方。受信任方计算输入的功能，并向各方返回各自的输出。

我们假设总是有一方被破坏。

The Definition

理想模型允许理想执行中的对手中止执行或在诚实方未获得输出的情况下获得输出。

参与方 $P_1,P_2$ ，敌手 $\mathcal{A}$ ，函数 $f:\{0,1\}^*\times \{0,1\}^* \rightarrow \{0,1\}^*\times \{0,1\}^*$ 的理想执行如下：

输入： $x(P_1),y(P_2),z(\mathcal{A})$ ，安全参数 $1^n$

向可信方发送输入：诚实参与方 $P_j$ 直接发送既定的输入给可信第三方。恶意参与方 $P_i$ 可能会发送abort（通过发送一个 $abort_i$ 的特殊消息）、发送既定的输入、发送等长的其他输入。这个决定由攻击者决定，可能是由 $P_i$ 的输入值和辅助值 $z$ 所影响的。定义发送给可信第三方的输入对为 $(x^\prime,y^\prime)$ 。

提前终止选项：如果可信第三方收到了输入 $abort_i$ ，那么可信第三方发送 $abort_i$ 给 $P_j$ 并结束执行。

可信方发送输出给攻击者：此时可信第三方计算得到 $f_1(x^\prime,y^\prime),f_2(x^\prime,y^\prime)$ 然后发送 $f_i(x^\prime,y^\prime),$ 给恶意参与方 $P_i$

攻击者命令可信方继续或中止：攻击者 $\mathcal{A}$ 发送 $comtinue$ 或者 $abort_i$ 给可信第三方。如果发送的是 $continue$ ，那么可信第三方把 $f_j(x^\prime.y^\prime)$ 发送给诚实参与方 $P_j$ 。如果攻击者 $\mathcal{A}$ 发送的是 $abort_i$ ，那么可信第三方发送 $abort_i$ 给诚实参与方 $P_j$ 。

输出：诚实参与方直接输出他从可信第三方中得到的输出值。恶意参与方什么都不输出。攻击者 $\mathcal{A}$ 根据恶意参与方的既定输入值、攻击者的辅助值、从可信第三方得到的输出 $f_j(x^\prime,y^\prime)$ ，输出任意的结果。

因此，一个理想执行的输出表示为 $IDEAL_{f,\mathcal{A}(z)}$

在真实模型中的执行中，不存在可信的第三方，对手 $\mathcal{A}$ 代替被破坏的一方发送所有信息，并且可以遵循任意多项式时间策略。与此相反，诚实的一方遵循协议 $\pi$ 的指令

真实协议的执行被记作 $REAL_{\pi,\mathcal{A}(z),i}(x,y,n)$

其中， $\pi$ 是协议，当 P1 和 P2 都诚实时，两方在分别输入 x 和 y 的情况下执行 $\pi$ 后分别输出 $f_1(x,y)$ 和 $f_2(x,y)$ ，安全参数是 $n$ ，辅助输入是 $z$

形式化定义

令 $f$ 是一个两方的functionality，令 $\pi$ 是一个两方的协议用于计算 $f$ 。如果对于现实模型下的所有的non-uniform概率多项式时间攻击者 $\mathcal{A}$ ，都存在一个对于理想模型下的non-uniform概率多项式时间的攻击者 $S$ ，满足对于 $i \in \{1,2\}$

\{IDEAL_{f,S(z),i}(x,y,n\}_{x,y,z,n}\stackrel{c}{\equiv}\{REAL_{\pi,\mathcal{A}(z),i}(x,y,n\}_{x,y,z,n}

其中 $x,y\in\{0,1\}^*.|x|=|y|,z\in \{0,1\}^*,n\in N$

那么则认为协议 $\pi$ 能够securely compute $f$ with abort in the presence of static malicious adversaries。

在本教程中，我们只考虑中止的安全性。因此，在后文中，当我们说 “安全地计算 ”时，其意图始终是终止计算。

请注意，上述式子包含了正确性和隐私性，因为理想分布和真实分布都包含了被破坏方和诚实方的输出。

Modular Sequential Composition

只要执行是按顺序进行的（即每次执行结束后才开始下一次执行），在顺序组合下安全的协议在多次运行时仍能保持其安全性。

模块化顺序组合：模块化顺序组合定理表述的基本思想是证明可以设计一个将理想功能作为子程序的协议，然后分析受信任方计算该功能时协议的安全性。

混合模型：双方运行一个协议 $\pi$ ，该协议包含对可信方的 “理想调用”，该调用计算一些功能 $f_1,...,f_{p(n)}$ 。这些理想调用只是向可信方发送输入的指令。收到受信任方的输出后，协议 $\pi$ 继续执行。协议 $\pi$ 规定，每 $i$ 次调用 $f_i$ 之前都要调用 $f_{i+1}$ 。诚实方在同一轮中向可信方发送其输入，在收到其输出之前不会发送其他信息。

协议 $\pi$ 的hybrid执行被记作

$HYBRID_{\pi,\mathcal{A}(z),i}^{f_1,...,f_{p(n)}}(x,y,n)$

其中，x，y是输入，x是辅助输入

设 $p(n)$ 为多项式，设 $f_1、...、f_{p(n)}$ 为双方概率多项式时间功能，设 $\rho$ 为协议，使得每个 $\rho_i$ 都能在存在恶意对手的情况下安全地计算 $f_i$ 。让 $g$ 是一个双方功能，让 $\pi$ 是一个在 $f_1,...,f_{p(n)}$ 混合模型中，在存在恶意对手的情况下安全计算 $g$ 的协议。那么， $\pi_{\rho_1,...,\rho_{p(n)}}$ 就能在存在恶意对手的情况下安全地计算 $g$ 。

Advanced Topics

Composition and Universal Composability

在现实世界中，许多安全和不安全的协议都是并发运行的，因此我们希望在这种情况下也能保证安全性。最流行的定义是通用可组合性（UC）

这个定义扩展了之前的定义，增加了一个环境机，它本质上是一个交互式区分器。环境机将输入写入各方的输入磁带，并读取它们的输出。此外，在整个执行过程中，它还与对手进行外部交互。环境的 “目标 ”是区分真实协议执行和理想执行。这一定义的一个非常重要的缺陷是，模拟器不能再在模拟中倒退对手。这是因为真正的对手实际上什么也做不了，只能执行环境的指令。现在，由于环境是真实对手和理想对手相互作用的外部机器，这意味着模拟器必须为外部对手进行模拟。由此可见，如果没有一个诚实的多数人，就不可能在没有任何可信设置的情况下安全地计算 UC 框架中的一大类功能。

一般 UC 框架相当复杂，因为它几乎可以为任何任务和任何环境建模。