混洗差分隐私（Shuffle-DP）已成为隐私保护去中心化数据分析的领先范式，吸引了学术界和工业界的广泛关注。然而，现有 Shuffle-DP 协议普遍依赖一个强假设：所有用户诚实执行协议。现实场景往往存在恶意用户（投毒攻击者），他们既可削弱甚至破坏隐私保护（如少加或不加噪声），也可破坏分析结果的可用性（如注入大量虚假消息，使聚合结果失去意义）。

针对 Shuffle-DP 下的投毒攻击防御，已有工作或仅能“检测”攻击而无法“恢复”有效结果，或局限于频数估计等单一任务，缺乏通用性。

本论文提出首个适用于所有并集保持查询的通用防御框架，在 Shuffle-DP 下既检测投毒攻击，又从被污染消息中恢复有意义的分析结果。

想了解 OceanBase 在产品技术核心竞争力及不同行业解决方案和最佳实践，可下载

《OceanBase 一体化分布式数据库》

核心理念：从“全诚实用户”到“存在投毒攻击者”

在 Shuffle-DP 中，消息经混洗后匿名，分析者无法区分其来自诚实用户还是攻击者。攻击者主要有两类行为：破坏隐私（少加或不加噪声，削弱整体隐私保护）、破坏效用（发送远超协议预期的消息数量，污染聚合结果，使误差极大甚至失去意义）。

本工作的目标是在“不改变仅依赖可信混洗、不依赖用户身份”的前提下，设计通用框架，实现：

1. 将任意 Shuffle-DP 协议改造成具备投毒攻击防御能力的版本；

2. 无攻击时误差与原始协议渐近等价；

3. 存在攻击者时误差仅增加多对数因子，恢复有意义的查询结果；

4. 通信与计算开销可控。

核心技术：层次化 Shuffle-DP（HSDP）

一个自然的防御思路是将每个用户隔离，各自独立执行一次 Shuffle-DP 协议，分析者分别检查每个用户的输出是否合理，再将有效结果聚合。这样攻击者最多只能影响自身对应的那一份输出，防御效果显著。然而，该方案的代价是将 n 个独立加噪结果直接相加，误差随 n 线性增长，远超原始协议的水平，实用性大打折扣。

误差过大的根本原因在于：完全隔离用户放弃了 Shuffle-DP 通过混洗聚合噪声、摊销误差的核心优势。为此，论文提出层次化 Shuffle-DP（HSDP），在保持防御能力的同时恢复这一优势。

HSDP 将 n 个用户组织成深度为 O(log n) 的二叉树：最底层每个叶子对应一个用户，逐层两两合并直至顶层覆盖全体用户。每个节点对应的用户组在组内联合执行一次 Shuffle-DP 协议，从而在组内实现噪声摊销。检测与恢复自底向上进行：对每个内部节点，分析者将该节点的聚合结果与其两个子节点结果之和进行比较，若偏差超过设定阈值则标记为“被污染”，并用子节点的有效结果递归替代。由于攻击者至多影响树中从叶子到根的一条路径，误差最多跨越 O(lo g n)层传播，最终误差相比原始协议仅增加 O(polylog n)因子，达到多对数级别的目标。

针对“攻击者少加噪声”的隐私破坏攻击，框架通过让诚实用户按参与规模对噪声进行缩放补偿，确保整体仍满足 (ε,δ)-DP。

图 1: HSDP 算法图示

HSDP 的通信开销相比原始协议增加了 O(polylog n) 倍：每个用户需参与 O(log ⁡n) 层 shuffle-DP 协议，隐私预算需要按照 O(log ⁡n) 分割；此外，在规模较小的底层分组中，为保证隐私每用户须贡献更多噪声消息，通信代价较高。

为此，论文提出对层次结构进行优化：将底层的分组规模从单用户扩大至 λ，减少需要独立执行协议的层数，从而显著降低底层的通信开销。通过适当选取 λ，可在误差与通信开销之间取得更优的平衡—— λ 越大，通信越高效，但被攻击者破坏的底层分组规模也相应增大，对误差略有影响。论文给出了 λ 的最优选取策略，并证明优化后每用户消息数可进一步压缩，同时误差保证不变。

通用框架：一键将任意 Shuffle-DP 协议升级为鲁棒版本

在层次化结构之上，论文表明：给定任意针对并集保持查询的 Shuffle-DP 协议，均可通过本框架转化为抗投毒攻击的版本。

随机器、混洗器、分析器均可作为黑盒复用，框架仅在外层增加“多层级调用 + 检测与恢复”逻辑。适用查询类型包括比特计数（bit counting）、求和（summation）、频数估计（frequency estimation）、区间计数（range counting）等所有并集保持查询；论文在比特计数、求和与频数估计上给出了具体实例与误差上界，并与现有最优协议对比（见下表 / 图2）。框架可扩展至常数 k 个攻击者，误差增加约 k 倍因子，并给出进一步通信优化思路。

本工作首次在 Shuffle-DP 下为所有并集保持查询提供“检测 + 恢复”的通用防御方案，且不依赖盲签名等额外密码学假设，适用范围大于仅支持频数估计且带强约束的已有工作。

表 1：协议对比表

性能与实验成果

论文在合成数据与真实数据集上对三种典型并集保持查询（比特计数、求和、频数估计）进行系统评估，将本框架与 GKMPS、BBGN、LWY、CSUZZ、CZ 等现有协议对比。

无攻击时，本框架与对应原始协议相对误差处于同一量级，验证“渐近等价”的理论结论。有攻击时，原始协议在投毒攻击下相对误差可飙升至数百甚至失效，而本框架能将相对误差稳定在较低水平（如 0.1%–1% 量级），成功恢复可用结果。在 Uniform、Zipf、Gauss 等分布以及 Adult、SF_Sal、BR_Sal、AOL 等真实数据上，本框架在有无攻击两种设定下均表现稳定，随用户数 n、隐私预算 ε、攻击者数量 k 等参数的变化与理论分析一致。通信方面，每用户消息数与每条消息比特数较原协议呈多对数倍增加，与理论分析相符，具备实际可部署性。

上述结果表明：本框架在保持隐私与通信效率的前提下，能有效防御 Shuffle-DP 下的投毒攻击并恢复高可用的分析结果。

表 2: 各协议在模拟数据集上的实验对比结果

表 3: 各协议在现实数据集上的实验对比结果

小结与展望

本论文针对 Shuffle-DP 模型中恶意用户发起的投毒攻击，提出首个面向所有并集保持查询的通用防御框架。通过层次化 Shuffle-DP 设计，在实现“检测 + 恢复”的同时，达到无攻击时与原始协议渐近等价的误差、存在常数个攻击者时仅多对数级别的误差增长。实验在合成与真实数据上验证了框架的有效性、通用性与效率。

论文同时指出若干开放问题与后续方向：能否将防御框架推广到非并集保持查询；如何在层次化结构下进一步借鉴现有工作降低通信开销等。这些问题的解决将进一步提升 Shuffle-DP 在开放、不可信用户环境下的可用性与安全性。

---

立即试用 OceanBase 企业版，体验国产数据库能力

180 天免费试用，零门槛开通