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

### 多洋葱：在节点变动环境下实现匿名性 在网络通信中，匿名性是一个重要的安全需求。尤其是在存在节点变动（churn）的动态网络环境中，实现匿名通信更具挑战性。本文将探讨洋葱路由协议在不同场景下的匿名性，以及如何解决现有解决方案的不足。 #### 1. 强匿名性游戏及相关定义 在强匿名性游戏 `StrongAnonGame(A, Π, L, λ)` 中，存在对手 `A` 和挑战者。游戏进行 `L` 轮，每一轮 `A` 会选择一个公告 `Bi`、一个节点变动时间表 `Ci`（在该轮中离线节点最多为 `c(N)` 个），以及两个有效的输入向量 `σi0` 和 `σi1`。`A` 将 `Bi`、`Ci` 对诚实节点的限制、`σi0` 和 `σi1` 发送给挑战者。然后，`A` 和挑战者根据公告 `Bi` 和节点变动时间表 `Ci` 与在线节点进行协议运行，挑战者代表诚实节点，`A` 代表腐败节点。 挑战阶段结束后，在最终阶段，`A` 可以通过提交 `ProcOnion` 查询与挑战者再次交互，但不能询问挑战阶段诚实节点形成的洋葱。最后，`A` 输出对挑战比特 `b` 的猜测 `b′`，若 `b′` 等于 `b`，则 `A` 赢得游戏。 基于此游戏，我们定义了几种强匿名性的变体： - **多轮与单轮**：若协议 `Π` 在多项式有界的 `L > 1` 情况下满足上述定义，则为多轮匿名；若 `L = 1` 时满足，则为单轮匿名。 - **强与弱**：若协议 `Π` 满足修改后的匿名性游戏定义（对手没有 `ProcOnion` 查询的预言机访问权限），则为弱匿名；若满足 `StrongAnonGame` 的定义，则为强匿名。 - **自适应与非自适应**：在 `StrongAnonGame` 中，对手是自适应的，可根据先前历史在每轮前选择公告、时间表和输入。非自适应匿名性定义则要求对手在观察任何协议运行之前选择所有输入、节点变动时间表和公告。 #### 2. 可模拟的洋葱路由协议 可模拟性是一种能将多轮匿名性简化为单轮匿名性的属性。如果一个可模拟的洋葱路由协议是单轮匿名的，那么可以通过一系列“模拟”额外轮次的归约证明它也是多轮匿名的。 可模拟性意味着归约应该能够仅使用其可访问的信息（即所有节点的公钥、公告、节点变动时间表、轮数和诚实节点的输入）重现诚实节点在一轮中的操作。考虑以下两种情况： - **真实场景**：`RealGame(A, Π, λ)` 由对手 `A`、洋葱路由协议 `Π`（具有洋葱加密方案 `(KeyGen, FormOnion, ProcOnion)`）和安全参数 `λ` 进行参数化。对手 `A` 选择对抗节点、公告、节点变动时间表、轮数和对抗节点的密钥，挑战者生成诚实节点的密钥。然后，`A` 选择输入向量，挑战者和 `A` 根据协议进行交互，最后 `A` 输出一个比特 `b`。 - **理想场景**：定义了两个算法： - 洋葱生成算法 `GenOnions`，输入安全参数、所有节点的公钥、公告、节点变动时间表、轮数、诚实节点的身份和输入，输出该诚实节点可能发送的洋葱集合。 - 调度算法 `ScheduleProcOnions`，输入安全参数、轮数、诚实节点的身份和该节点在该轮的状态，输出从该轮开始要处理的洋葱集合和更新后的状态。 `IdealGame(A, GenOnions, ScheduleP