多洋葱：在节点变动环境下实现匿名性

### 多洋葱：在节点变动环境下实现匿名性 #### 1. 相关工作概述 现有的洋葱路由工作存在多种局限性： - 部分工作缺乏理论建模和可证明的安全性，或者偏离了不可区分性的标准概念。 - 有些仅关注洋葱的构建，而未讨论或分析路由算法。 - 一些只考虑单轮静态网络环境下的路由。 - 还有部分工作聚焦于下限研究。 #### 2. 问题建模 我们的模型基于实际的洋葱路由（如Tor），考虑了网络节点的变动（churn）。在Tor中，有五到十个半可信的目录权威机构维护中继节点的最新信息，路由器会定期上传“路由器描述符”，目录权威机构每12到18小时更新其对路由器的视图，用户和路由器从多个目录权威机构下载更新视图的“差异”信息。 在我们的模型中： - **时间**：假设为同步设置，时间以轮为单位，多个轮构成一个大的运行周期。设运行周期为$R_1, ..., R_L$，且$L$受安全参数$\lambda$的多项式约束。 - **参与方**：有$N$个参与方$P_1, ..., P_N$，$N$也受$\lambda$的多项式约束，每个参与方都有一个公开的密钥。设$Bad$为受破坏的参与方集合。 - **节点变动公告**：公告$B_1, ..., B_L$准确指示每个运行周期开始时哪些参与方在线。即$B_i \subseteq \{P_1, ..., P_N\}$，参与方$P_j$在运行周期$R_i$开始时在线当且仅当$P_j \in B_i$。 - **节点变动时间表**：$C_1, ..., C_L$为运行周期的节点变动时间表。对于每个$i$，$C_i$是参与方 - 轮次对的集合，如$C_i = \{(P_{i1}, r_1), (P_{i2}, r_2), ...\}$，表示在运行周期$R_i$中，参与方$P_{ij}$在第$r_j$轮开始时离线。所有在$C_i$列表中的参与方在运行周期开始时必须根据$B_i$在线。为简化，我们允许参与方仅在运行周期开始时上线，而不在运行期间上线。 - **节点变动限制**：设$c(N)$为节点变动限制，即任何时刻最多有$c(N)$个参与方离线。要求公告和节点变动时间表指定的离线参与方数量不超过$c(N)$，即对于每个$i$，$N - |B_i| + |C_i| \leq c(N)$。 - **输入**：运行周期$R_i$的输入表示为向量$\sigma_i = (\sigma_{i,1}, \sigma_{i,2}, ..., \sigma_{i,N})$，其中$\sigma_{i,j}$是参与方$P_j$的输入。每个参与方的输入要么是收件人 - 消息对$(P_k, m)$，表示该参与方将消息$m$发送给参与方$P_k$，要么是$\perp$，表示该参与方在该运行周期不发送信息。输入向量$\sigma_i$有效需满足存在一个置换$f : [B_i] \to [B_i]$，使得对于每个$P_j \in B_i$，$P_j$的输入是$(f(P_j), m_j)$，且对于每个$P_j \notin B_i$，输入为$\perp$。 我们使用基于游戏的方法定义匿名性，允许对手选择洋葱路由协议的一对输入，其目标是通过运行协议确定挑战者选择的是哪个输入。为防止对手轻易获胜，对手必须从同一等价类中选择两个输入。两个输入向量$\sigma$和$\sigma'$关于受破坏参与方集合$Bad$等价，记为$\sigma \equiv_{Bad} \sigma'$，当且仅当对于所有$P_j \in Bad$，$\sigma_j = \sigma'_j$，且$P_j$作为收件人的诚实消息内容在$\sigma$和$\sigma'$中相同。 #### 3. 对手模型 对手可以控制节点变动、观察网络流量，并选择破坏的参与方（如果有）。我们假设通信是经过认证的，对手只能丢弃受破坏或离线参与方发送的消息，不能干扰两个诚实且在线参与方之间的通信。定义了三类不同能力的对手： |对手类型|能力描述| | ---- | ---- | |网络对手|可以控制节点变动、观察网络流量| |被动对手|除网络对手的能力外，还能破坏一定比例的参与方并观察这些参与方的计算和状态，但不能控制它们偏离协议| |主动对手|具备被动对手的所有能力，还能控制受破坏的参与方做任何事情，包括偏离协议| #### 4. 面向节点变动的洋葱加密 我们对双洋葱加密进行了推广，每个洋葱的每一层有两个候选中间服务器。为解决受破坏参与方可能选择受破坏候选服务器的问题，引入了辅助参与方（helpe