匿名举报的下界技术概述

### 匿名举报的下界技术概述 #### 1. 匿名传输基础 匿名传输（Anonymous Transfer，简称 AT）是一种重要的技术，在许多安全场景中都有应用。这里主要聚焦于两方匿名传输，涉及一个发送方、一个虚拟方和一个外部接收方。发送方输入要传输的消息 μ，发送方和虚拟方在同步轮次中交换消息，虚拟方仅发送随机比特。传输执行跨越 c 轮交互，每一轮双方都发送一条消息。外部接收方可以根据完整的传输记录尝试重构原始消息。 - **正确性误差**：如果重构过程无法恢复消息 μ 的概率至多为 ε，则称该 AT 具有 ε 正确性误差。 - **匿名性**：如果没有敌手在识别两个参与方中谁是发送方时，其优势超过随机猜测的优势 δ，则称该 AT 是 δ - 匿名的，且敌手可以选择要发送的消息。 在这种设定下，存在如下关于 AT 的下界： 对于所有多项式时间敌手，具有 ε - 正确性和 δ - 匿名性且包含 c 轮的两方（静默接收方）AT，满足 δ · c ≥ (1 - ε) / 2 - 1 / m(λ) ，其中 m(λ) 是任意多项式。这意味着，在假设参与者是多项式时间的情况下（即 c = poly(λ) ），不存在同时满足 δ 和 ε 为可忽略函数（negl(λ) ）的 AT。 该下界存在一定局限性： - 它没有排除存在匿名性 δ 随轮数 c 呈逆多项式缩放的 AT 协议，例如 δ = 1 / c 。这表明通过大量交互，正确性和安全性之间的权衡可能会得到改善。 - 对应此下界的攻击需要多项式次数地调用诚实算法（即使该多项式可以任意小），这为“非常细粒度”的协议留下了空间，在这些协议中，安全性仅对运行时间比诚实用户略超线性的敌手成立。 #### 2. 攻击的通用蓝图 所有攻击的核心思想是与 AT 的任何（可能是部分的）传输记录相关联的简单进度概念。具体做法是，为 AT 的部分传输记录关联一个实数值 p ∈ [0, 1] ： - 可以通过用均匀随机消息替换所有缺失的消息来完成任何部分传输记录，并尝试从发送方恢复输入消息 μ ← {0, 1}^ℓ 。对于部分传输记录，将 p 定义为随机完成该记录后能够恢复 μ 的概率。 - 随着传输记录变长，将 p 的部分变化归因于协议中的各方。例如，在参与方 A 发送传输记录中的第 i 条消息后，协议的值从 p(i - 1) 变为 p(i) ，则将与 p(i - 1) 和 p(i) 相关的某种进度归因于 A 。 观察到： - 空传输记录的值 p(0) = 1 / 2^ℓ 接近 0（如果 μ 是均匀随机选择的）。 - 根据正确性，完整传输记录的期望值 p(2c) = 1 - ε 接近 1。 由于虚拟参与者发送的消息不会显著改变部分传输记录的值（因为在随机完成传输记录时，虚拟方的消息遵循其真实分布），并且只要最终值 p(2c) 明显大于初始值 p(0) ，就必须在某个时刻取得显著的总进度。因此，发送方的消息必须显著地将部分传输记录的值偏向 1。 基于此，识别 AT 发送方的蓝图如下： 1. 估计各方对总进度的贡献，即与最后一条消息由该方发送的部分传输记录相关联的 p 值的变化。 2. 论证： - 虚拟方的总体贡献可能较小。 - 双方的总贡献（在期望上）相当大。 3. 由此得出，其消息对增加 p 值贡献最大的一方很可能是 AT 发送方。 #### 3. 隐蔽作弊游戏 将上述攻击蓝图抽象为一种自然的游戏，称为隐蔽作弊游戏。该游戏由两个玩家 A 和 B 进行，他们在实数区间 [0, 1] 上交替移动一个点（即游戏的当前状态），共进行 2c 轮。其中一个玩家是偏差诱导者，另一个是中立方。初始状态是 p(0) ，最终状态 p(2c) 要么是 0 要么是 1。 如果无论偏差诱导者是谁，都有 E[p(2c)] ≥ p(f) ，则称一个策略的成功率为 p(f) > p(0) 。中立方只能进行随机移动，且在期望上不影响当前状态。第三个玩家（观察者 C）的目标是根据游戏状态确定哪个玩家是偏差诱导者。 该抽象的意义在于，攻击以特定的黑盒方式使用 AT，即仅用于测量值 p ∈ [0, 1] ，并以黑盒方式使用所有 AT 算法。这种将对 AT 的攻击抽象为游戏策略的方式，捕捉了一类自然的黑盒区分算法，涵盖了大多数对 AT 的合理攻击。 #### 4. 通用“免费午餐”攻击 这是对上述游戏的第一种攻击，对应于一个定理的证明概要。该攻击非常简单，仅利用了以下事实：在随机移动的期望下，偏差诱导者的移动会使结果产生一个加性项 (p(f) - p(0)) / c ，而中立方的移动不会增加任何偏差。 假设游戏由 c 轮组成（每轮包括玩家 A 和 B 各移动一次），且玩家 A 先移动，那么 A 进行奇数轮（2k + 1）的移动，B 进行偶数轮（2k）的移动。策略如下： - 随机选择 A 的一次移动 k ← [c] ，其第 k 次移动使游戏状态从 p(2k) 变为 p(2k + 1) 。 - 以概率 p(2k + 1) 输出“A 是偏差诱导者” ，以概率 1 - p(2k + 1) 输出“B 是偏差诱导者” 。 如果 A 是中立方，那么在期望上 p(2k + 1) = p(2k) ，该策略以概率 p(k) 输出 A 。如果 A 是偏差诱导者，该策略以概率 p(2k + 1) 输出 A 。由于 B 是中立方，B 的总期望贡献为 0 ，即 E[k][p(2k + 2) - p(2k + 1)] = 0 ，因此该算法在确定 A 是否为偏差诱导者时的优势为 E[k][p(2k + 1) - p(2k)] = (p(f) - p(0)) / c 。 该攻击的成本是获得一个概率为 p(2k + 1) 的单个样本的成本，对应于运行一次诚实用户算法的成本（即尝试重构随机选择的以 A 的消息结尾的部分传输记录的随机完成后的消息）。这表明，在任何细粒度的设置中（只要敌手和诚实用户处于相同的复杂度类），不存在具有特定参数安全性的 AT 。 #### 5. 具有大优势的通用攻击 这种攻击稍微复杂一些，但能实现更强的优势，代价是运行时间为更大的多项式时间。其灵感来自于对中立方移动在期望上不改变游戏状态这一限制的深入观察。当当前游戏状态 p 接近 0 时，这一限制更为严格。例如，当 p = 1 / 2 时，中立方可能以 1 / 2 的概率将状态移动到 p' = 0 或 p' = 1 ，导致 p 值发生较大变化；但当 p ⪆ 0 时，根据马尔可夫不等式，p' 不能太大。 因此，考虑一种不同的进度量化方式，即与移动和玩家相关的乘法形式的进度。如果游戏的第 i 次移动将游戏状态从 p(i - 1) 变为 p(i) ，则将与该移动相关的乘法进度定义为 r(i) = p(i) / p(i - 1) 。一个玩家的总进度是其所有移动相关进度的乘积。 在这种情况下，所有移动的总进度为： ∏(i∈[2c]) r(i) = ∏(i∈[2c]) p(i) / p(i - 1) = p(f) / p(0) 这意味着，（在期望上）其中一个玩家的进度至少为 √(p(f) / p(0)) 。并且，可以证明中立方移动的 r(i) 乘积在期望上为 1 。根据马尔可夫不等式，中立方的 r(i) 乘积大于或等于 √(p(f) / p(0)) 的概率至多为 √(p(0) / p(f)) 。 这表明，以概率 1 - √(p(0) / p(f)) ，发送方的总贡献较大，虚拟方的贡献较小，攻击者至少可以以此概率识别出他们。 然而，观察者无法直接访问实数值 p ∈ [0, 1] ，只能以概率 p 采样硬币。这导致了一个问题：从多项式时间观察者的角度来看，在只有采样访问的情况下，p = negl(λ) 和 p = 0 是不可区分的，那么如何确保比率 r(i) = p(i) / p(i - 1) 是有定义的（即 p(i - 1) ≠ 0 ）？ 解决方案是，将乘积限制在 i ≥ i* 的移动上，使得对于所有 i > i* ，p(i) ≥ τ ，其中 τ 是一个小的精度阈值，满足 p(0) < τ < p(f) （例如 τ = 1 / poly(λ) ），并约定 p(i*) = τ 。这样，比率就有了定义，总贡献现在变为 p(f) / τ 。 通过联合边界论证，以足够高的概率 1 - c√(τ / p(f)) ，虚拟方的所有“后缀乘积”都较小（即小于 √(p(f) / τ) ）。 最终的观察者策略是使用切尔诺夫界（Chernoff）将所有 p(i) 估计到足够好的精度，以确保 r(i) = p(i) / p(i - 1) 的乘积准确，只要乘积中出现的所有 p(i) 项相对于阈值 τ 足够大。 该攻击的主要优势在于，其关联攻击的优势与轮数无关，只有运行时间随轮数缩放（以确保使用切尔诺夫界时具有足够的精度），这从数量上证明了乘法进度更适合在隐蔽作弊游戏中识别偏差。 #### 6. 扩展到 N 方情况 可以将上述攻击扩展到 N 方设置，即一个发送方与 N - 1 个虚拟方进行交互。步骤如下： 1. 上述攻击可以直接转化为有针对性的预测攻击，即在给定发送方是 [N] 中的参与方 i 或 j （i ≠ j 且对有针对性的预测器是固定的）的承诺下，能够正确识别发送方。这是因为可以从任何 N 方 AT 构建一个两方 AT ，同时保留有针对性的预测安全性。 2. 为了获得不依赖任何额外信息就能正确输出发送方身份的通用预测攻击，可以将任何有针对性的预测攻击升级为标准预测攻击，同时保留优势 δ ： - 攻击对所有不同索引对 {(i, j) | i, j ∈ [N], i ≠ j} 运行有针对性的预测攻击。 - 输出在所有运行 (i*, j) （j ≠ i* ）中都被指定为发送方的参与方 i* 。如果不存在这样的索引，则输出参与方 1。 如果 i* 是 N 方 AT 的发送方，根据联合边界，所有内部运行 (i*, j) （j ≠ i* ）的有针对性的预测攻击都正确指出 i* 是发送方的概率至少为 δ' ≥ 1 - N(1 - δ) 。从定理 1 的攻击开始，设置 α' = N · α ，可以在 N 方设置中获得与定理 1 相同的下界，但攻击的运行时间会有一个 poly(N) 的开销。 #### 7. 预备知识和定义 ##### 7.1 符号说明 - 当 X 是一个分布或遵循该分布的随机变量时，x ← X 表示根据分布 X 采样 x 。 - 如果 X 是一个集合，x ← X 表示从 X 中均匀随机采样 x 。 - 如果 Alg 是一个随机算法，x ← Alg 表示使用均匀随机硬币采样 Alg 的输出。 - [k] 表示集合 {1, ... , k} ，其中 k ∈ N ，[0, 1] 表示实数区间 {x ∈ R | 0 ≤ x ≤ 1} 。 - negl(λ) 表示满足 f(λ) = 1 / ω(1) 的函数 f 。 ##### 7.2 切尔诺夫界 使用如下（乘法形式）的切尔诺夫 - 霍夫丁不等式（Chernoff - Hoeffding inequality）： 假设 X1, ... , Xn 是独立的伯努利变量，其共同均值为 p 。对于所有 t > 0 ，有： Pr[ ∑(i = 1 to n) Xi ∉ [(1 - t) · np, (1 + t) · np] ] ≤ 2e^(-2t²p²n) ##### 7.3 匿名传输的定义 两方（静默接收方）匿名传输（AT） Π(ℓ)_AT ，具有正确性误差 ε ∈ [0, 1] 、匿名性 δ ∈ [0, 1] 、由 c ∈ N 轮组成且消息长度为 ℓ ∈ N （所有这些都可能是 λ 的函数），是一个由概率多项式时间（，PPT）算法（Setup, Transfer, Reconstruct）组成的元组，具体规格如下： - **Setup(1^λ)** ：输入安全参数 λ 的一元编码，输出一个公共参考字符串 crs 。 - **Transfer(crs, b, μ)** ：输入公共参考字符串 crs 、发送方的索引 b ∈ {0, 1} 、要传输的消息 μ ∈ {0, 1}^ℓ ，输出一个传输记录 π 。传输记录 π 由发送方和虚拟方之间的 c 轮交互组成，虚拟方（索引为 1 - b ）在每一轮发送均匀独立的消息，发送方的每条消息取决于到目前为止的部分传输记录，其下一条消息函数由 Transfer(crs, b, μ) 隐式定义。默认情况下，假设接收方不发送任何消息（即接收方是静默的）。 - **Reconstruct(crs, π)** ：输入公共参考字符串 crs 和传输记录 π ，输出一条消息 μ' ∈ {0, 1}^ℓ 。默认情况下，假设 Reconstruct 是确定性的。 需要满足以下属性： - **ε - 正确性**：对于所有足够大的安全参数 λ 、索引 b ∈ {0, 1} 、消息长度 ℓ ∈ poly(λ) 以及所有消息 μ ∈ {0, 1}^ℓ ，有： Pr[ crs ← Setup(1^λ); π ← Transfer(crs, b, μ); μ' ← Reconstruct(crs, π); : μ' ≠ μ ] ≤ ε - **δ - 匿名性**：对于所有 PPT 算法 D 、所有足够大的安全参数 λ 、消息长度 ℓ ∈ poly(λ) 以及所有消息 μ ∈ {0, 1}^ℓ ，有： | Pr[π(0) ← Transfer(crs, 0, m) : D(π(0)) = 1] - Pr[π(1) ← Transfer(crs, 1, m) : D(π(1)) = 1] | ≤ δ 如果上述等式对于所有区分器 D ∈ C 成立，则称 Π(ℓ)_AT 相对于敌手类 C 是 δ - 匿名的。 如果发送方的下一条消息函数（由 Transfer(crs, b, μ) 隐式定义，其中 b 是发送方）不依赖于 b ，并且 Reconstruct 不依赖于参与者的身份，则称该匿名传输是对称的。 此外，关于匿名传输还有以下几点说明： - 与其他定义相比，这里的符号和定义略有不同但等价。随着 ε 和 δ 减小，AT 具有更强的正确性和匿名性保证，这与其他一些定义相反。 - 接收方可以被设为静默的，因为其随机磁带可以硬编码在公共参考字符串 CRS 中。 - Reconstruct 可以假设为确定性的，因为其随机硬币可以采样并包含在公共参考字符串 crs 中。 - 当参与方数量为 N 时，δ 的定义是相对于在 N 个参与者中随机猜测的优势。在两方设置中，基于不可区分性的定义和基于预测的定义是等价的，但在 N 方设置中，这种等价性并非显而易见，不过可以证明在一定参数损失的情况下仍然成立。 以下是一些总结表格： | 攻击类型 | 优势 | 运行时间 | 特点 | | ---- | ---- | ---- | ---- | | 通用“免费午餐”攻击 | (p(f) - p(0)) / c | 运行一次诚实用户算法的成本 | 简单，优势与轮数有关 | | 具有大优势的通用攻击 | 较大，与轮数无关 | 随轮数呈多项式增长 | 复杂，优势不依赖轮数 | mermaid 格式流程图如下： ```mermaid graph TD; A[开始] --> B[初始化 AT 协议]; B --> C[进行交互轮次]; C --> D{是否达到 c 轮}; D -- 否 --> C; D -- 是 --> E[接收方尝试重构消息]; E --> F{重构是否成功}; F -- 是 --> G[记录成功情况]; F -- 否 --> H[记录失败情况]; G --> I[进行攻击判断]; H --> I; I --> J[输出攻击结果]; J --> K[结束]; ``` 以上就是关于匿名传输的技术概述，包括基本概念、攻击方法以及扩展到多参与方的情况。通过这些分析，可以更好地理解匿名传输的安全性和局限性。 ### 匿名举报的下界技术概述 #### 7. 匿名传输的关键特性总结 为了更清晰地理解匿名传输（AT），下面对其关键特性进行总结： | 特性 | 描述 | | ---- | ---- | | 正确性误差 ε | 重构消息失败的概率上限，ε 越小，正确性越强 | | 匿名性 δ | 敌手识别发送方的优势上限，δ 越小，匿名性越强 | | 轮数 c | 发送方和虚拟方交互的轮数，影响协议的复杂度和安全性 | | 消息长度 ℓ | 要传输消息的比特长度 | 这些特性相互关联，共同决定了 AT 协议的性能和安全性。例如，在某些情况下，增加轮数 c 可能会提高匿名性，但也会增加协议的运行时间和复杂度。 #### 8. 攻击方法的对比分析 前面介绍了两种攻击方法，下面对它们进行详细的对比分析： | 攻击类型 | 优势计算方式 | 运行时间复杂度 | 适用场景 | | ---- | ---- | ---- | ---- | | 通用“免费午餐”攻击 | (p(f) - p(0)) / c | 运行一次诚实用户算法的成本 | 对攻击复杂度要求较低，轮数较少的场景 | | 具有大优势的通用攻击 | 与轮数无关，优势较大 | 随轮数呈多项式增长 | 对攻击优势要求较高，轮数较多的场景 | 通用“免费午餐”攻击简单直接，其优势与轮数相关，适合在轮数较少的情况下使用。而具有大优势的通用攻击虽然运行时间较长，但优势不依赖于轮数，在轮数较多时能提供更可靠的攻击效果。 #### 9. 从两方到 N 方扩展的详细分析 将攻击从两方扩展到 N 方是一个重要的步骤，下面详细分析这个过程： - **有针对性的预测攻击**：可以从任何 N 方 AT 构建一个两方 AT ，从而将两方攻击直接转化为有针对性的预测攻击。这个过程的关键在于将除了指定的两个参与方 i 和 j 之外的所有消息视为新两方协议的公共参考字符串（CRS）的一部分。 - **升级为通用预测攻击**：为了获得不依赖额外信息的通用预测攻击，需要对所有不同索引对 {(i, j) | i, j ∈ [N], i ≠ j} 运行有针对性的预测攻击。然后输出在所有运行 (i*, j) （j ≠ i* ）中都被指定为发送方的参与方 i* 。如果不存在这样的索引，则输出参与方 1。 这个扩展过程虽然增加了攻击的复杂度，但通过合理的设计和优化，可以在 N 方设置中保持与两方设置相似的安全性和优势。 #### 10. 实际应用中的考虑因素 在实际应用中，使用匿名传输协议和相关攻击方法时，需要考虑以下因素： - **安全性与性能的平衡**：增加轮数 c 可以提高匿名性，但会降低协议的性能。因此，需要根据具体应用场景来平衡安全性和性能。 - **敌手的能力**：不同的敌手可能具有不同的计算能力和攻击策略。在设计协议和攻击方法时，需要考虑敌手的能力范围。 - **协议的可扩展性**：随着参与方数量的增加，协议的复杂度和安全性会发生变化。因此，协议需要具有良好的可扩展性。 #### 11. 未来发展方向 匿名传输技术在不断发展，未来可能会朝着以下方向发展： - **更高效的协议设计**：研究如何设计更高效的匿名传输协议，在保证安全性的前提下，降低协议的运行时间和复杂度。 - **更强的安全性保证**：探索新的安全模型和攻击方法，提高匿名传输协议的安全性。 - **多领域应用**：将匿名传输技术应用到更多的领域，如金融、医疗等，保护用户的隐私和数据安全。 #### 12. 总结与展望 匿名传输是一种重要的安全技术，在保护用户隐私和数据安全方面具有重要作用。通过对匿名传输的基本概念、攻击方法以及扩展到多参与方的情况进行分析，我们可以更好地理解其安全性和局限性。 在实际应用中，需要根据具体场景来选择合适的协议和攻击方法，平衡安全性和性能。未来，随着技术的不断发展，匿名传输技术有望在更多领域得到应用，并提供更强的安全性保证。 以下是另一个 mermaid 格式流程图，展示从两方攻击扩展到 N 方攻击的过程： ```mermaid graph TD; A[开始] --> B[选择 N 方 AT 协议]; B --> C[构建两方 AT 协议]; C --> D[进行有针对性的预测攻击]; D --> E[对所有索引对运行攻击]; E --> F{是否有唯一指定的发送方}; F -- 是 --> G[输出指定的发送方 i*]; F -- 否 --> H[输出参与方 1]; G --> I[结束]; H --> I; ``` 综上所述，匿名传输技术具有广阔的发展前景，但也面临着一些挑战。通过不断的研究和创新，我们可以进一步提高其安全性和性能，为用户提供更可靠的隐私保护。