恶意安全多方PSI协议的优化与攻击分析

### 恶意安全多方PSI协议的优化与攻击分析 #### 1. 多输出PSI扩展攻击 在恶意环境下，将多方PSI协议扩展以支持多输出并非易事，因为各方可能无法忠实地传递交集输出。Garimella等人将单输出PSI协议扩展为支持多输出的协议，实现了较高效率。然而，这里提出了一种针对该多输出扩展的简单实用攻击方法。 - **多输出扩展流程** 1. 所有参与方$P_0, P_1, \cdots, P_n$公开对其OKVS $\{Q_i\}_{i\in[0,n]}$进行承诺，即每个参与方$P_i$向其他所有方广播承诺$com_i = Commit(Q_i; r_i)$，其中$r_i$是随机数。 2. 所有承诺完成后，各方打开这些承诺。对于$i \in [0, n]$，每个参与方$P_i$将$(Q_i, r_i)$发送给其他所有方，并验证所有打开的正确性（即检查对于所有$j \neq i$，$com_j = Commit(Q_j; r_j)$）。 3. 每个参与方$P_i$（$i \in [0, n]$）计算输出为$\{h \in X_i | \sum_{j=0}^{n} Decode(Q_j, h) = 0\}$。 - **攻击步骤** 1. 攻击者$A$接收所有$i \notin C$（$C$是被破坏方的集合）的OKVS $Q_i$，其中包括$Q_0$。$Q_i$（$i \notin C$，$i \neq 0$）定义为$Q_i = Encode(\{(h, H(PRF_i(h), h) + s_{i,h}) | h \in X_i\})$，$Q_0$计算为$Q_0 = Encode(\{(h, s_{0,h} - \sum_{i=1}^{n} H(PRF_i(h), h)) | h \in X_0\})$。 2. 攻击者$A$计算$Q := \sum_{i \notin C} Q_i$。根据零共享的定义，对于任何$h$，有$\sum_{i \in [0,n]} s_{i,h} = 0$。因此，对于每个$h \in \bigcap_{i \notin C} X_i$，可得$\sum_{i \notin C} Decode(Q_i, h) = - \sum_{i \in C} s_{i,h} - \sum_{i \in C} H(PRF_i(h), h)$。 3. 攻击者$A$破坏$i \in C$的参与方$P_i$，当知道任何$h$时，可计算所有$i \in C$的份额$s_{i,h}$和值$PRF_i(h)$。对于任何$h \notin \bigcap_{i \in [0,n]} X_i$，攻击者$A$可以通过检查上述等式是否成立来判断$h \in \bigcap_{i \notin C} X_i$。对于$\bigcap_{i \notin C} X_i$中熵较低的项，攻击者$A$可以通过枚举项并检查其正确性来直接揭示这些项，从而获取$\bigcap_{i \notin C} X_i$中包含的秘密数据。 - **攻击示例**：在特殊情况下，只有$P_0$是诚实的，其他所有方都被破坏（即$|C| = n$），攻击者可以通过执行上述攻击泄露集合$X_0$中的一些秘密项。这是因为诚实的中央方$P_0$揭示了OKVS $Q_0$，而在原始的仅$P_0$获取输出的多方PSI协议中，$P_0$仅在本地使用$Q_0$。 以下是攻击步骤的mermaid流程图： ```mermaid graph LR A[接 ```