高效基于OT的乘法协议解析

### 高效基于OT的乘法协议解析 #### 1. 协议成本与应用 在随机预言机模型（ROM）中，执行一批 $m$ 次乘法并具备 $2^{-\kappa/4}$ 的恶意安全性时，成本如下表所示： | 项目 | 成本 | | ---- | ---- | | OT调用次数 | $m · ℓ + \kappa$ | | 通信量（比特） | $(m + 20) · ℓ$ 比特 | | 计算量（群指数运算） | 30 | 对于较大的 $m$ 值，即使包含正确性检查，该协议相较于 Gilboa 的诚实但好奇协议，复杂度增加并不显著。 该协议有以下几个重要应用： - **OLE 和 VOLE**： - 不经意线性评估（OLE）可视为两方乘法的变体，其中一方（如 P2）可完全控制其份额。对于输入 $a$（P1）和 $(b, \sigma)$（P2），该功能会向 P1 返回 $ab + \sigma$，而 P2 无返回值。 - 向量不经意线性评估（VOLE）是 OLE 的重要扩展，假设 P2 持有向量对 $(b, \sigma)$，P1 可得知组合值 $ab + \sigma$。OLE 和 VOLE 可分别直接简化为乘法和批量乘法，因此该协议（经恶意安全性编译）可用于此目的。 - **MAC 和乘法三元组**： - **消息认证码（MAC）**：对于 P1 的秘密输入 $x$，两方 MAC 功能会向 P1 返回 $\tau \in Z_q$，向 P2 返回 $(k, \sigma) \in Z_q^2$，满足 $\tau = x · k + \sigma$。这使得被破坏的 P1 实际上对 $x$ 做出承诺，可通过揭示 $(x, \tau)$ 进行认证。 - **认证乘法三元组**：在无输入的情况下，认证乘法三元组功能（Beaver）会分别向 P1 和 P2 返回 $(a_1, b_1, c_1)$ 和 $(a_2, b_2, c_2)$，满足 $(a_1 + a_2) · (b_1 + b_2) = c_1 + c_2$，同时为所有相关数据提供 MAC 密钥和份额。 下面是使用该协议生成 MAC 和三元组的流程： ```mermaid graph LR classDef startend fill:#F5EBFF,stroke:#BE8FED,stroke-width:2px; classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; classDef decision fill:#FFF6CC,stroke:#FFBC52,stroke-width:2px; A([开始]):::startend --> B(生成 MAC 或三元组):::process B --> C{是否为 MAC 生成}:::decision C -->|是| D(使用批量乘法协议):::process C -->|否| E(运行基础协议生成三元组):::process D --> F(进行正确性检查):::process E --> G(运行批量协议生成 MAC 数据):::process G --> F F --> H([结束]):::startend ``` #### 2. 与其他协议的比较 - **与 MASCOT 比较**：MASCOT 是唯一纯基于 OT 生成具有恶意安全性三元组的工作。对于 MAC 功能，P2 采样随机 MAC 密钥 $k$，双方运行 Gilboa 协议两次。为验证 P1 的诚实性，P1 需揭示 $x_0$ 和 $x$ 的随机组合及其 MAC 份额的相同随机组合。对于 Beaver 功能，根据目标安全性，需运行 Gilboa 协议 18 或 20 次。而使用该协议生成单个三元组，在随机预言机模型中的成本如下： | 项目 | 成本 | | ---- | ---- | | OT 调用次数 | $4\kappa + 8\ell$ | | 通信量（比特） | $70\ell$ | | 计算量（群指数运算） | 90 | 当 $\ell \approx 512$ 且目标安全性为 $2^{-64}$ 时，该协议在底层 OT 使用上比 MASCOT 便宜 53%。 - **与 [12] 中的 2PC 乘法比较**：[12] 中的核心两方乘法协议是 MASCOT 的变体，对于每个指定输入的乘法，需使用 OT 进行两次随机乘法。而该协议仅需进行一次随机乘法，避免了冗余，在底层 OT 使用上有 2 倍的提升。 #### 3. 相关工作 - **基于噪声编码的乘法**：Ishai 等人推广了他们的协议，支持 P2 输入的多种编码方式。在各种编码假设下，多种编码方案可产生复杂度显著改善的诚实但好奇乘法协议。在特定编码假设下，该方法可实现恶意安全性。 - **非基于 OT 的乘法**： - **基于同态加密（HE）的乘法**：可基于部分同态加密或全同态加密。 - **基于同态和函数秘密共享的新方法**：Boyle 等人展示了如何使用同态秘密共享生成 OLE 相关性和长 VOLE 实例，这些新方法在通信成本上有改进。 #### 4. 协议安全分析技术 恶意攻击者 $A$ 破坏 P1 时，可能提供与任何 $a \in Z_q$ 不一致