简介

传统差分隐私（DP）大多假设：所有记录共用同一个隐私预算 𝜀。在很多实际场景中，这个假设过强且缺乏泛用性。比如银行估计总存款时，大额账户往往需要更强保护；平台分析用户行为时，部分敏感人群可能需要更高隐私等级；在联邦学习中，不同样本、不同客户的隐私诉求也不尽相同。

为满足这类需求，学界提出了 Per-record Differential Privacy（PrDP）。即每条记录的隐私预算由其内容决定。如果我们用 𝑟 表示一条记录，便可以用函数 E(𝑟) 来刻画“这条记录需要多强的保护”。然而，E(𝑟) 与数据值强相关，连“隐私预算本身”也变成需要保护的隐私，使得设计既安全又高效的算法十分困难。

本文工作提出了首个针对 PrDP/PrLDP 的通用框架：在不泄露隐私预算的前提下，把任意标准 DP / LDP 机制“一键升级”为 per-record 版本，并且误差几乎只依赖于当前数据集中真正出现记录的最小隐私预算 𝜀_min(𝐷)，而不是全局极端最小值 𝜀ˇ。

核心理念：从“统一预算”到“每条记录有自己的隐私预算”

在 PrDP 模型下，每条记录 𝑟 都有一个由内容决定的隐私预算 E(𝑟)，范围在 [𝜀ˇ, 𝜀ˆ]之间。直观做法是，取全局最小预算 𝜀ˇ，当成普通 DP 的统一预算去跑所有算法。

但这会带来两大痛点：

首先是实用性问题，𝜀ˇ  对应的是“极端敏感的假想记录”，现实中几乎不会出现，但误差却被强行放大到和 1/𝜀ˇ 成正比，严重牺牲可用性。

其次是隐私问题，若算法在噪声尺度等行为上泄露出数据库中实际的最小隐私预算，𝜀_min(𝐷)，就等同于向外界泄露了“这条记录有多敏感”，相当于泄露了这条记录的隐私。

该论文希望能够找到一种方法，满足以下条件：

1. 不假设事先知道 𝜀_min(𝐷)，也不暴露每条记录的隐私预算 E(𝑟)；

2. 误差依赖 𝜀_min(𝐷)，而不是 𝜀ˇ；

3.  能兼容“任何一种标准 DP / LDP 机制”。

为此，作者提出了两项核心技术分别用于针对中心化场景和分布式场景：

• 隐私域划分（Privacy-specified Domain Partitioning）——用于中心化 PrDP；

• 隐私域查询扩增（Privacy-specified Query Augmentation）——用于分布式 PrLDP。

核心技术一：隐私域划分——把“难的全局问题”拆成“局部小问题”

在中心化 PrDP 下，框架首先对预算区间 [𝜀ˇ, 𝜀ˆ] 做按对数尺度的分桶，把记录划分到不同的“隐私域”中。每个隐私域 Xᵢ 对应一段预算区间（例如(2^{i-1}𝜀ˇ, 2^{i}𝜀ˇ]）。

然后在每个域上，算法用该域的“下界预算”做一次标准 DP 计数。这样一来，不同隐私域之间通过并行组合保证整体满足 PrDP。这一步得到了一套 PrDP 计数基元，误差已经可以做到 𝑂~(1/𝜀_min(𝐷))，为后续通用框架打下基础。

利用上面的 PrDP 计数基元，在每个隐私域上估计一个带噪声的计数；设计一套数据相关的阈值规则，从低预算的隐私域开始“向上扫”；找到第一个“记录足够多”的域 X_ℓ，把它的下界预算记为 𝜀_𝜏；把预算小于 𝜀_𝜏 那一小撮记录安全地“丢掉”（它们数量有限，对结果影响可以控制在理论误差之内）。这样得到的 𝜀_𝜏 既不会过小，又不会泄露真实的 𝜀_min(𝐷)，可以证明它与 𝜀_min(𝐷) 只差一个双对数因子。

图1:PrDP 的 Count 算法图示

通用框架：一键把任意 DP 机制升级成 PrDP 版本

在拿到 𝜀_𝜏 后，框架就可以做一件很“工程友好”的事：把任意标准 𝜀-DP 机制 M，当成黑盒直接复用。具体流程是，在估计 𝜀_𝜏 的过程中，只用掉一部分隐私预算，用剩余的一半预算，在“过滤后的数据集 𝐷_ℓ ”上调用原来的 DP 机制 M，把 𝜀 设置成 𝜀_𝜏 /2。

通过理论分析证明，该框架的总误差包含两部分，即 M 在 𝜀_min(𝐷) 下的误差和少量舍弃记录带来的偏差。对于计数、求和、最大值等经典查询，论文详细论证了 PrDP 下使用该框架的误差几乎与目前已知最优 DP 机制在相同量级，并且证明框架下“几乎最优”。

除去这三个详细讨论的问题之外，该框架的通用性极强，对于任何已知的普通 DP 算法，该框架都可以无痛将其转换为支持 PrDP 设定，并且不限制隐私函数的具体形式。

图2:PrDP的通用框架算法图示。

PrLDP：本地差分隐私下的 per-record 保护

为了进一步扩展该框架的适用性，作者给出了在分布式 DP 场景中的一套方案。

分布式场景的难点是，每条记录要在本地加噪声再上报，但噪声尺度又取决于 E(𝑟)，直接暴露噪声大小就会泄露隐私预算。为此，论文提出了 Privacy-specified Query Augmentation（隐私域查询扩增）。

首先同样把预算区间划成若干隐私域；对每条记录 𝑟，构造一组“在各个隐私域上的计数查询” Qᵢ(𝑟) = I(𝑟∈ Xᵢ)。这样可以通过类似本地方案中的方法利用设定阈值直接选出一个合适 𝜀_𝜏，让大部分数据都在该隐私预算之上，但 𝜀_𝜏 又不过小，以至于引入过多的后续噪音。

随后，对于具体的查询，本地统一用同一套 LDP 协议（例如加 Laplace 噪声或随机响应）回答这些查询。和 PrDP 的通用框架类似，该 PrLDP 框架可以支持任何已有的 LDP 协议，将其转化成一套可以解决 PrLDP 隐私需求的方法。

最终文章论证了，该 PrLDP 框架在误差上基本达到了与原来 LDP 机制在预算 𝜀_min(𝐷) 下同一个量级的误差，只额外付出常数与 log 因子。这也是首个系统性研究 per-record local DP 的工作，大大拓展了该领域的研究场景。

性能成果

论文使用了四个真实金融相关数据集（银行账户、旧金山工资、Ontario 工资、日本贸易）以及多个合成数据集，对多种等任务进行了系统评估。

在 PrDP 场景下，对比直接使用全局最小预算 𝜀ˇ 的 基础方案，以及最先进的 Personalized DP（PDP）方法（可以证明，PDP 是 PrDP 的一种特殊形式，PDP 提供的隐私保护更弱），PrDP 框架在误差上整体提升 2×–165×，同时保持良好效率，并且在不同数据规模、不同隐私预算函数下，框架都能稳定工作，验证了其通用性。

在最大值估计任务上，基础方案由于依赖 𝜀ˇ 而直接失效，而 PrDP 框架依旧可以在多种数据集上把最大相对排名误差控制在约 6% 左右。

同时，作者开源了实现代码，方便社区在此基础上扩展更多 DP 应用。

表1: PrDP 通用框架相较于 PDP（PDP 相较 PrDP 提供更弱隐私保护）下最先进算法有显著的准确率和性能优势。

图3: PrDP 框架相较其他基线算法在不同数据量和不同隐私函数下均有明显优势。

图4: PrDP 框架相较其他基线算法在不同数据偏度和不同隐私函数下均有明显优势。

图5: PrDP 框架相较其他基线算法在不同先验知识和不同隐私函数下均有明显优势

小结与展望

这项工作给出的 Per-record Differential Privacy 通用框架，为“每条记录有不同隐私需求”这一现实问题提供了系统解法。

在理论上，本文首次证明任意标准 DP / LDP 机制都可以在误差近似不变的前提下升级为 PrDP / PrLDP。在实践中，在多个真实金融场景上显著提升了精度与速度。论文也提出了若干后续方向：从静态数据库扩展到流式与持续发布场景，让 𝜀_min(𝐷) 随时间演化时依然可控以及探索在 Shuffle-DP 等新型分布式模型下的 per-record 隐私分配。

在线咨询

优质资料下载

往期推荐

▼ 点击「阅读原文」，查看论文