小条目集合的改进私有集合交集协议

### 小条目集合的改进私有集合交集协议 #### 1. 哈希方法与多项式插值成本 不同哈希方法在进行多项式插值时的成本有所不同： - 广义布谷鸟哈希（GCH）：$N = 0.65n$ 且 $d = 3$，执行 $N$ 次多项式插值的成本非常小。 - 双选择哈希：$N = 0.33n$ 且 $d = 4$，执行 $N$ 次多项式插值的成本也较小。 - 简单哈希：$N = n/10$ 且 $d \approx 46$，执行 $N$ 次多项式插值的成本较高，但执行 $n/10$ 次 46 度插值仍然相当快。 | 哈希方法 | $N$ 值 | $d$ 值 | 多项式插值成本 | | ---- | ---- | ---- | ---- | | 广义布谷鸟哈希（GCH） | $0.65n$ | 3 | 非常小 | | 双选择哈希 | $0.33n$ | 4 | 较小 | | 简单哈希 | $n/10$ | $\approx 46$ | 较高 | #### 2. 基于 mOPRF 的恶意私有集合交集协议 提出了一种基于 BaRK - OPRF 和简单哈希结合基于置换的哈希函数的恶意安全私有集合交集（PSI）协议。 **参数设置**： - 发送方 Alice 和接收方 Bob 分别有输入集合 $X = \{x_1, x_2, ..., x_n\} \in F_p$ 和 $Y = \{y_1, y_2, ..., y_n\} \in F_p$，所有元素的位长为 $\ell$。 - 随机哈希函数 $h : \{0, 1\}^* \to [N]$。 - 基于置换的哈希函数 $Per_h,X$ 将集合 $X$ 映射到表 $B_X$，该表由 $N$ 个桶组成，每个桶有 $d$ 个槽，其中 $Nd > |X|$，且 $d = O(1)$。记 $Per(x) := (i, x')$，其中 $x'$ 是 $x$ 在桶 $i$ 中存储的值，由 $h$ 和 $x$ 定义，且 $Per^{-1}(i, x') = x$。 **协议步骤**： 1. Bob 使用 $Per$ 将 $Y$ 映射到 $B_Y$，对于 $B_Y[i]$ 中每个桶的空槽，放入一个长度为 $\ell - \log N$ 的虚拟项。 2. Alice 发送（sender, id），Bob 发送（receiver, id, $B_Y$）到 $F_{oprf}$，然后： - Bob 接收 $Y' = \{F(i, y') | y' \in B_Y[i]\}_{i\leq N}$。 3. 对于每个 $x \in X$，Alice 向 $F_{oprf}$ 查询 $x$，输入为 $(i, x')$ 使得 $Per(x) = (i, x')$，然后 Alice 得到 $F(i, x')$。Alice 向 Bob 发送 $U = \{F(i, x') | x \in X \land Per(x) = (i, x')\}$。 4. 对于每个 $y \in Y$，若 $Per(y) = (i, y')$ 且 $F(i, y') \in U$，则 Bob 输出 $y$ 作为交集中的元素。 ```mermaid graph TD; A[Bob: 映射 Y 到 BY 并填充虚拟项] --> B[Alice 发送(sender, id) 且 Bob 发送(receiver, id, BY) 到 Foprf]; B --> C[Bob 接收 Y']; B --> D[Alice 查询 X 到 Foprf 并得到 F(i, x')]; D --> E[Alice 发送 U 给 Bob]; E --> F[Bob 判断 F(i, y') 是否在 U 中]; F --> G[Bob 输出交集元素]; ``` 在恶意环境下，当发送方被破坏时，模拟需要从对 $F_{oprf}$ 的查询和集合 $U$ 中提取发送方的输入集合 $X$。为避免碰撞，一种方法是选择 $v = 2\kappa$，但这会显著增加通信开销。另一种方法是仅提取 PRF 唯一且出现在 $U$ 中的元素。 该协议的估计通信开销为 $Nd(\ell - \log N)+(\kappa + \log n)n + o(n)$，且在 $F_{oprf}$ 混合模型下，针对恶意对手具有统计安全性。 #### 3.