安全子线性通信采样协议详解

### 安全子线性通信采样协议详解 在数据处理和安全通信领域，采样协议是一项关键技术。本文将详细介绍几种不同类型的安全采样协议，包括 L1、L2、Lp 采样以及两党乘积采样，并分析它们的特性、实现方式和安全性。 #### 1. 安全 L1 采样协议 玩具协议存在安全性问题，攻击者可能通过破坏 P1 来获取信息。为解决这一问题，我们采用了无感知采样的方法。 ##### 1.1 无感知采样框架 - 双方根据 w1 的 L1 分布无感知地采样 i1，输出索引 i1 在双方之间秘密共享，记为 ⟨i1⟩。同样，根据 w2 的 L1 分布无感知地采样 ⟨i2⟩。 - 执行安全的两方协议来完成后续计算： - 以偏置 p 抛硬币得到 b。 - 如果 b = 0，输出 i1 的解密结果；否则输出 i2 的解密结果。 ##### 1.2 理想功能定义 - **Fosample(L1)**：用于无感知 L1 采样的理想功能。它接收发送方的 n 维权重向量 w，以 $ \frac{w_i}{\|w\|_1} $ 的概率采样 i，选择随机填充 π 并分别发送给发送方和接收方。 - **FbiasCoin**：用于有偏硬币抛掷的理想功能。它接收 P1 和 P2 的输入 s1 和 s2，以 $ p = \frac{s_1}{s_1 + s_2} $ 的偏置抛硬币，选择随机位 r 并发送给双方。 ##### 1.3 L1 采样协议 协议 1 是在 (Fosample(L1), FbiasCoin)-混合模型中实现 FL1 的两方 L1 采样协议，步骤如下： 1. 以 P1 为发送方，输入 w1，P2 为接收方，执行 Fosample(L1)，得到输出索引的秘密共享 ⟨i1⟩。 2. 以 P2 为发送方，输入 w2，P1 为接收方，执行 Fosample(L1)，得到输出索引的秘密共享 ⟨i2⟩。 3. 执行 FbiasCoin，P1 输入 ∥w1∥1，P2 输入 ∥w2∥1，得到输出位的秘密共享 ⟨b⟩。 4. 执行 F2PC 计算电路，输入为 ⟨i1⟩、⟨i2⟩、⟨b⟩，输出为 i1 · (1 - b) + i2 · b。 该协议在半诚实安全模型下安全地实现了 FL1。 ##### 1.4 实现 Fosample(L1) 通过阈值全同态加密（FHE）来安全地实现 Fosample(L1)，协议 2 步骤如下： 1. 发送方计算 s := ∥w∥1。 2. 发送方和接收方执行 F2PC 从 [0, s) 中均匀采样 r，r 的秘密共享分别为 r1 和 r2。 3. 双方设置阈值 FHE 方案，明文空间为 GF(2)。 4. 接收方发送 r2，发送方计算 r := r1 ⊕ r2。 5. 发送方同态评估电路： - 初始化 cnt0 = 0，对于 j = 1, ..., n，计算 cntj = cntj + wj。 - 输出满足 r ∈ [cnti - 1, cnti] 的 i，记为 i。 6. 发送方选择随机填充 π，发送 c = i ⊕ π 给接收方。 7. 双方进行阈值解密，接收方得到 c 的解密结果。 8. 发送方输出 π，接收方输出 c 的解密结果。 在假设存在具有 IND - CPA 安全性的阈值 FHE 的情况下，该协议在半诚实安全模型下安全地实现了 Fosample(L1)。 #### 2. 两方 L2 采样 给定输入向量 w1 和 w2，L2 采样功能从分布 DL2(w1, w2) 中采样，其概率质量函数为 $ Pr[D_{L2}(w_1, w_2) samples i] = \frac{(w_{1,i} + w_{2,i})^2}{\sum_j (w_{1,j} + w_{2,j})^2} = \frac{(w_{1,i} + w_{2,i})^2}{\|w_1 + w_2\|_2^2} $。 ##### 2.1 非私有 L2 采样协议 为了实现 L2 采样，我们引入了辅助分布 Dignore。 - **Dignore 定义**：对于输入向量 w1 和 w2，Dignore(w1, w2) 忽略 DL2(w1, w2) 中的交叉项，以 $ \frac{w_{1,i}^2 + w_{2,i}^2}{\|w_1\|_2^2 + \|w_2\|_2^2} $ 的概率采样 i。 - **协议步骤**： 1. 双方运行 Πignore 从 Dignore(w1, w2) 中采样得到输出 i。 2. 双方交换 wb,i 和 $ \|w_b\|_2^2 $，计算 $ Pr_{D_{ignore}(w_1, w_2)}[i] $ 和 fc(w1, w2, i)。 3. 以 $ \frac{fc(w_1, w_2, i