如何混淆多方计算输入

### 如何混淆多方计算输入 #### 1. 研究背景与相关工作 在服务器被攻破的情况下，攻击者获得的信息不应超过对某些剩余函数的预言机访问权限。此前，在 [强] 非对称密码认证密钥交换（aPAKE）和 Thomas 等人的研究中，都探讨过类似性质的具体实例。而本次研究对这种安全属性和构造进行了系统化整理。 在一些多方计算（MPC）模型中，也存在泄露预言机访问权限的概念。例如，在非交互式多方计算（NIMPC）和单轮计算模型中，各方在协议中仅发言一次，但不同模型的通信模式有所差异。在这些模型中，某些类型的破坏可能使攻击者能无限次地在不同输入上重新执行协议，从而了解函数在许多输入上的输出。因此，这些模型中最佳的安全性是协议泄露的信息不超过对剩余函数的预言机访问权限。 不过，此前的工作与本次研究存在重要差异。在 NIMPC 协议和单轮协议中，剩余函数可通过预言机查询完全学习到，而本次研究针对的是不可学习的剩余函数，如点函数和超平面成员查询。并且，此前在 NIMPC 模型中的工作以不可区分混淆（iO）的方式定义安全性，不利于可组合安全，而本次研究明确要求虚拟黑盒（VBB）风格的安全性，并在通用可组合（UC）框架中定义安全性。 #### 2. 预备知识 - **理想化模型**：在理想化模型中，所有参与方都可访问某个指数级大的随机对象。随机预言机模型中的随机对象是一个函数 $H : \{0, 1\}^* \to \{0, 1\}^n$，理想置换模型中的随机对象是一对互为逆函数的 $\Pi, \Pi^{-1} : X \to X$。此外，还考虑了通用群模型。 - **混淆** - **定义 1**：设 $C_f = \{f(x, \cdot) | x \in \{0, 1\}^*\}$ 是一类函数。$C_f$（在 $Ora$ 理想化模型中）的混淆是一个多项式时间算法元组 $(Obf, ObfEval)$，其中 $Obf^{Ora}(x)$ 输出一个混淆程序 $O_x$，$ObfEval^{Ora}(O_x, y)$ 输出 $f$ 值域中的一个值 $z$。若对于所有的 $x, y$，都有 $ObfEval^{Ora}(Obf^{Ora}(x), y) = f(x, y)$ 且具有压倒性概率，则该混淆满足正确性。 - **定义 2**：若存在一个多项式函数 $c$，使得对于所有的 $x, y$，$ObfEval^{Ora}(O_x, y)$ 对其 $Ora$ 预言机进行 $c(\kappa)$ 次查询，则 $C_f$ 的混淆 $(Obf, ObfEval)$ 具有与输入无关的查询复杂度。在本文中，将具有此属性的混淆称为三元组 $(Obf, ObfEval, c)$。 - **定义 3**：若存在一个多项式时间模拟器 $Sim = (Sim_0, Sim_1)$，使得对于任何多项式时间攻击者 $A$ 和任何 $x$，分布 $\{O_x \leftarrow Obf^{Ora}(x); A^{Ora}(O_x)\}$（真实交互）和 $\{(O_x, state) \leftarrow Sim_1(); A^{Sim_{f(x, \cdot)}}_2(state)(O_x)\}$（理想交互）不可区分，并且在理想交互中 $Q_S \leq r \cdot \frac{Q_A}{c}$（其中 $Q_S$ 是 $Sim_2$ 对其函数预言机的查询次数，$Q_A$ 是 $A$ 对其预言机接口的查询次数），则混淆 $(Obf, ObfEval, c)$ 具有模拟率为 $r$ 的虚拟黑盒（VBB）安全性。 - **定义 4**：若对于任何多项式时间攻击者 $A$，存在一个多项式时间算法 $Extract$，使得 $Pr[ObfEval^{Ora}(O, y) \neq f(x, y) : (y, O) \leftarrow A^{Ora}, x := Extract(O, H)]$ 可忽略不计（其中 $H$ 是 $A$ 的查询列表），则 $C_f$ 的 VBB 混淆 $(Obf, ObfEval, c)$ 是可提取的。 标准模型下的 VBB 混淆虽然存在，但本次研究的构造需要比 VBB 更强的条件。标准模型下的 VBB 混淆允许评估者以 0 次预言机查询的代价在无界数量的输入上学习 $f(x, \cdot)$，这使得定义 3 中的模拟率为无穷大。本次研究的协议范式与（至少非平凡的）标准模型 VBB 不兼容，但 io2PC 的思想在标准模型 VBB 中是可行的。不过，该协议无法实现特定的 io2PC 功能，因为模拟器无法从 $O_x$ 中提取 $x$，也无法在服务器被攻破后提取攻击者对 $f(x, \cdot)$ 的预言机查询。 #### 3. 定义 io2PC io2PC 可直观地看作是 VBB 混淆在交互式环境中的扩展，服务器可能会长期存储其混淆后的输入。其理想功能如下： |参数|详情| | ---- | ---- | |客户端 C、服务器 S 和理想攻击者 $A^*$| - | |存储|三个映射：状态（status）、预算（budget）和输入（input）| 具体命令处理流程如下： 1. **初始化（Init）**：服务器 S 发送命令 $(Init, sid, x)$ 时，若状态 $status[sid]$ 已定义则忽略该消息；否则，将状态设置为活动（active），存储输入 $x$，将预算设置为 0，并向 $A^*$ 发送 $(Init, sid, S)$。 2. **服务器被攻破（Compromise）**：攻击者 $A^*$ 发送命令 $(Compromise, sid)$ 时，将状态 $status[sid]$ 设置为被攻破（compromised）。 3. **离线评估（OfflineEval）**：若 $P = A^*$ 且状态 $status[sid] \neq$ 被攻破或服务器 S 是诚实的，则忽略该消息；若状态未定义，则向 $P$ 发送 $(IOEval, sid, \perp)$；否则，检索输入 $x$ 并向 $P$ 发送 $(OfflineEval, sid, f(x, y))$。 4. **在线评估（IOEval）**：若服务器 S 是诚实的，则检索存储的输入 $x$；否则，使用替