如何混淆多方计算（MPC）输入

### 如何混淆多方计算（MPC）输入 #### 1. 个性化通用群协议 在理想置换模型中，我们可使用通用群来实现个性化通用群协议。为避免混淆，我们需区分公共群和个性化群： - **公共群**：协议使用的通用群，双方可无限制地访问该群的操作。群元素句柄通过一个名为 `dlog` 的映射与它们的离散对数相关联。在安全证明中，模拟器可充当此通用群，并以不同方式维护 `dlog` 映射。 - **个性化群**：由协议实现，其理想功能中，句柄通过名为 `DLog` 的映射与离散对数相关联。该群的目标是通过交互式协议，严格限制客户端对涉及 `DLog` 的操作的访问。 ##### 1.1 主要思想 个性化通用群的“密钥”由强伪随机置换（PRP）`F` 的密钥 `k`（正向和逆向评估分别表示为 `F +` 和 `F -`）以及公共群的随机生成元 `g` 组成。离散对数为 `x` 的个性化群元素由形式为 `(Fk(m), gxgm)` 的句柄表示，其中 `m ∈ Z` 提供乘法盲化因子 `gm`。这种编码方式的原理如下： - 若客户端不知个性化群的“密钥”，由于 `F ± k` 的行为不可预测，客户端只能创建随机元素的句柄。 - 若攻击者攻破服务器并获取“密钥” `(k, g)`，可反转 PRP 得到 `m`，然后去除 `gm` 盲化项，得到 `gx`。此时，攻击者可在无服务器帮助的情况下，对 `gx` 形式的无盲化值执行群操作，但模拟器仍可观察这些操作。 在服务器的帮助下，客户端可对两个句柄执行群操作： 1. 考虑两个句柄 `(c1, g1)` 和 `(c2, g2)`，其中 `c1 = Fk(m1)`，`c2 = Fk(m2)`，`g1 = gx1gm1`，`g2 = gx2gm2`。客户端可计算 `g3 = g1g2 = gx1+x2gm1+m2`，这是离散对数为 `x1 + x2` 的元素的有效句柄的一半。若客户端能获得 `Fk(m1 + m2)` 的加密值，就能构建完整且正确的句柄。 2. 客户端和服务器运行两方计算（2PC）协议，客户端提供 `c1` 和 `c2`，服务器提供 `k`，客户端学习 `Fk(m1 + m2)`，而服务器不获取任何信息。此 2PC 协议不涉及公共通用群中的群操作，仅涉及指数运算和 PRP 评估。 同样，在服务器的帮助下，客户端可执行零测试： 1. 给定句柄 `(c1, g1)`，客户端想知道 `c1` 是否为 `Fk(m1)` 形式，以及 `g1` 是否为 `g0gm1 = gm1` 形式，即客户端需了解 `c1` 是否对 `g1` 的离散对数进行了加密。 2. 我们借助 2PC 协议实现此功能。客户端提供 `c1`，服务器提供 `k`，在 2PC 功能中获取 `m1`。该功能提供两个基本操作：首先，选择随机数 `s`，让客户端使用计算得到的 `m1` 值学习 `gs·m1`；其次，允许客户端将其选择的任何群元素提升到 `s` 次幂。若客户端选择计算 `gs 1`，则结果等于 `gs·m1` 当且仅当 `g1 = gm1`。 ##### 1.2 详细信息 协议的完整细节如图 8 所示，各方调用的单独 2PC 功能如图 7 所示。此“辅助功能”是典型的反应式功能，可通过任何标准 2PC 协议安全实现。但由于技术原因，协议需进行一些必要修改： - **句柄包装**：句柄被包装在理想置换 `Π±` 中，有效句柄 `h` 的形式为 `Π(c1, g1)`，其中 `c1` 和 `g1` 如上述定义。借助理想置换，模拟器可观察每次新句柄生成或现有句柄解包为两个组件的过程。 - **避免历史泄露**：在原始方案中，客户端可获取新句柄 `Π(Fk(m1+m2), gx1+x2gm1+m2)`，但这会向持有 `k` 的人泄露其“历史”信息。因此，新句柄应使用新的掩码 `m3`，而非从父句柄派生的 `m1 + m2`。当各方运行 2PC 让客户端学习新密文时，客户端应学习 `Fk(m3)`，并获取校正项 `Δ = gm3−m1−m2` 以完成句柄。由于 2PC 功能本身无法生成群元素，此任务委托给服务器。 为防止服务器作弊，功能使用一次性消息认证码（MAC）对群元素进行认证。功能向客户端提供随机 MAC 密钥 `α` 和 `β`，向服务器提供 `s` 及其一次性 MAC `μ = αs + β`。服务器向客户端发送 `gs` 和 `gμ`，客户端通过 `(gs)α · gβ?= (gμ)` 检查指数中的 MAC。 零测试协议有两个概念步骤比概述更复杂： 1. **客户端学习 `gm1s`**：2PC 辅助功能希望客户端学习群元素 `gm1s`，此任务委托给服务器，并使用一次性 MAC 确保客户端收到预期的群元素。为防止服务器得知 `m1`，功能向客户端提供随机数 `z`，要求服务器交付 `gm1s+z`，客户端通过乘以 `g−z` 解盲。 2. **服务器执行盲指数运算**：2PC 功能向服务器提供 `s`，使服务器参与盲指数运算协议（将客户端选择的群元素提升到 `s` 次幂）。为确保服务器正确执行操作，功能向客户端交付 `gs`，并让服务器运行简单的可验证指数运算协议，使客户端确信其群元素确实被提升到 `s` 次幂。 ##### 1.3 安全分析 当 `F` 为强 PRP 时，图 8 中的协议在通用群和理想置换模型中，可 UC 安全地实现图 6 中的 `Fpgg` 功能。 - **服务器被破坏的情况**：在 `OnlineMult` 和 `OnlineZeroTest` 期间，服务器的视图不包含客户端句柄选择的任何信息，因为所有通信都通过辅助功能 `Fhelper` 进行。`Fpgg` 功能允许被破坏的服务器学习任何句柄的离散对数，并直接注册具有选定离散对数的句柄。模拟器可利用这些功能拦截攻击者的 `Π±` 预言机查询，并在功能和实际群元素之间中继离散对数信息。 - **客户端被破坏的情况**：在现实世界中，句柄的形式为 `h = Π(c, gDLog[h]gF −1 k (c))`。我们使用符号离散对数技术来模拟攻击者对某些值的无知。攻击者不知道 `g` 的离散对数，用形式变量 `K` 表示；在会话被破坏前，攻击者不知道任何 `c` 的 `F −1 k (c)`，用形式变量 `Mc` 表示；攻击者最初对 `DLog[h]` 值一无所知，用形式变量 `Dh` 表示。 攻击者只能通过零测试获取公共群中群元素的信息。当攻击者进行零测试时，模拟器观察并检查该群元素的 `dlog` 值。此 `dlog` 是形式变量上的符号表达式，若该表达式作为这些变量的函数在符号上不等于零，则现实世界中的零测试成功的概率可忽略不计，模拟器可直接判定零测试失败。但 `dlog` 表达式可能包含表示具体 `DLog[h]` 值的 `Dh` 项，此时模拟器需知道具体的 `DLog` 值是否使 `dlog` 表达式恒等于零。经分析，这种情况仅在模拟器需知道单个 `DLog[h]` 值是否为零，且攻击者对 `h` 进行了 `OnlineZeroTest` 后才会发生。在会话被破坏前，其他情况下具体的 `DLog` 值对 `dlog` 表达式是否符号为零无影响。 当攻击者破坏会话并获取 PRP 密钥 `k` 时，`F −1 k (c)` 值不再不确定。模拟器在破坏后将每个形式变量 `Mc` 替换为具体值 `F −1 k (c)`，这改变了攻击者能在 `dlog` 中产生的表达式类型。破坏后，更多情况下具体的 `DLog[h]` 值会影响 `dlog` 表达式是否符号为零，此时模拟器可使用 `OfflineMult` 和 `OfflineZeroTest` 了解相关的 `DLog` 值信息。 以下是相关的功能和协议代码： **个性化通用群功能 `Fpgg`**： ```plaintext Parameters: – group order p – handle length ℓ – client C and server S Storage: – map DLog; our convention is uninitialized entries of DLog are sampled uniformly from Zp before being used. – map status On input (Init, sid, h ∈{0, 1}ℓ) from server S: 1. If status[sid] already defined: abort. 2. Set status[sid] := active. 3. Send (Init, sid, S, h) to C. 4. Set DLog[h] := 1. On (Compromise, sid) from A∗: 5. Set status[sid] := compromised. On input (OnlineMult, sid, ssid, h1, h2) from C: 6. Give (OnlineMult, sid, ssid) to S and await response (Deliver, sid, ssid) 7. Sample h3 ←{0, 1}ℓ. 8. Set DLog[h3] := DLog[h1] + DLog[h2] mod p. 9. Give (OnlineMult, sid, ssid, h3) to P. On input (OfflineMult, sid, ssid, u0, (u1, h1), . . . , (un, hn)) from party P ```