匿名举报与匿名传输的下界分析及匿名置换路由协议研究

### 匿名举报与匿名传输的下界分析及匿名置换路由协议研究 在当今数字化信息广泛流通的时代，数据访问和传输的安全性与匿名性愈发重要。我们将探讨匿名举报、匿名传输以及匿名置换路由等相关领域的研究成果，包括相关协议的分析、技术挑战以及解决方案。 #### 匿名举报的优势分析 在匿名举报相关研究中，策略 $C^*$ 具有一定优势。其优势可以通过以下公式体现： $$ \left| \Pr\left( CO(A) = 1 \right) - \Pr\left( CO(B) = 1 \right) \right| \geq \Pr\left( CO(A) = 1 \right) - \Pr\left( CO(B) = 1 \right) \geq p_f - 4c\sqrt{\tau} + \frac{1 - p_f}{2} - 1 + \left( p_f - 4c\sqrt{\tau} + \frac{1 - p_f}{2} \right) - negl(\lambda) = p_f - 8c\sqrt{\tau} - negl(\lambda) $$ 将证明开始时的参数代入，可得 $8c\sqrt{\tau} = \frac{1}{\alpha}$，从而完成证明。 这里有两个重要的备注： - **正确预测**：攻击不仅能区分，还能正确输出偏差诱导者的身份。即 $\Pr\left( CO(A) = 1 \right) - \Pr\left( CO(B) = 1 \right) = p_f - 8c\sqrt{\tau} - negl(\lambda)$，这一特性在后续扩展到多方情况时至关重要。 - **攻击成本和细粒度保证**：策略 $C^*$ 的采样复杂度是一个较大但固定的多项式 $c^6 \cdot \alpha^4 \cdot \omega(\log^2 \lambda)$。在特定设置下，能获得具有恒定优势的攻击，且具有固定的采样成本开销。 #### 匿名传输与隐蔽作弊游戏的关联 对于匿名传输问题，我们可以将其与隐蔽作弊游戏建立联系。 ##### 定理7 假设有一个双方匿名传输协议 $\Pi_{\ell}^{AT}$，具有正确性误差 $\varepsilon \in [0, 1]_{\mathbb{R}}$，对于一类对手 $C$ 具有匿名性 $\delta \in [0, 1]_{\mathbb{R}}$，协议包含 $c \in \mathbb{N}$ 轮，消息长度为 $\ell \in \mathbb{N}$，且满足确定性重建。那么存在一个隐蔽作弊游戏以及玩家策略，该游戏包含 $c$ 轮，游戏的初始状态为 $2^{-\ell}$，期望最终状态为 $p_f = 1 - \varepsilon$，并且玩家策略能以 $\delta$ 欺骗 $C$ 中的观察者。此外，如果 $\Pi_{\ell}^{AT}$ 是对称的，那么隐蔽作弊游戏也是对称的。 证明过程如下： - **玩家和角色**：游戏玩家为匿名传输协议的参与者。偏差诱导者是使用均匀随机消息 $\mu \leftarrow \{0, 1\}^{\ell}$ 的发送者，中立方是虚拟方，观察者是区分者。 - **执行和状态**：隐蔽作弊游戏中的移动是匿名传输协议中发送的消息。对于游戏的一次执行，即完整的匿名传输协议转录 $\pi \leftarrow Transfer(crs, b, \mu)$，其中 $crs \leftarrow Setup(1^{\lambda})$ 且 $\mu \leftarrow \{0, 1\}^{\ell}$。游戏的相关状态 $p_i$（$i \in [2c]$）定义为：$p_i = p(crs, \pi[i]) := \Pr\left( \mu' \leftarrow Reconstruct(crs, \pi[i]) : \mu' = \mu \right)$，其中 $\pi[i]$ 是协议 $Transfer$ 的前 $i$ 条消息组成的部分转录，$\pi[i]$ 是随机完成的部分转录的分布。游戏的初始状态 $p_0 = \frac{1}{2^{\ell}}$，由于协议的正确性误差为 $\varepsilon$，所以隐蔽作弊策略的成功率 $p_f = 1 - \varepsilon$，且最终状态 $p_{2c} \in \{0, 1\}$。 - **中立方的限制**：在匿名传输协议中，虚拟消息是均匀随机采样的，因此与随机完成得到的对应消息具有相同的分布。例如，假设 $A$ 是偏差诱导者/发送者，对于所有 $k \in [c]$，$(\pi[2k - 1] \parallel msg)$（其中 $msg$ 是随机的匿名传输协议消息）和 $\pi[2k - 1]$ 具有相同的分布，所以 $E[X_{2k}^{(B)} | X_{2k - 1}, \cdots, X_0] = X_{2k - 1}$。 - **观察者和安全性**：给定匿名传输协议的转录，我们可以实现一个采样预言机。输入 $i$ 时，