Machanavajjhala l-Diversity 2007 — 给匿名分组补上敏感值多样性

待复核

是什么

日常类比：老师把成绩单姓名涂掉，还把座位号改成“第三排附近”，但第三排附近 4 个人全都挂科，大家还是能猜到某个同学挂科了。 l-Diversity 说的是：每个匿名小组里，敏感答案不能只剩一种或几乎一种；至少要有 l 个“站得住”的可能答案。

k-anonymity 只保证“你像至少 k 个人”，挡住的是把一行重新对回真人。 l-diversity 继续追问：就算别人不知道哪一行是你，他能不能从这个小组的敏感列直接猜出你的病、收入、职业？

一句话定义：发布微数据时，每个准标识符等价类里，敏感属性至少有 l 个充分代表的取值，这张表才算 l-diverse。它是 k-anonymity 的补丁，不是最终答案；它修的是“组里全是同一种秘密”和“攻击者有背景知识”这两类洞。

为什么重要

不理解 l-Diversity，下面这些事都没法解释：

为什么“每组 4 个人”仍然可能泄露疾病：如果 4 个人全是 cancer，匿名组本身就泄密
为什么攻击者的常识会变成武器：知道某些人群低概率患某病，就能排除选项
为什么匿名化的核心不是只数人头，还要看敏感值分布
为什么传统匿名化永远抓不到差分隐私的水位：它保护发布后的表形状，却不保证“某个人在不在数据里时输出几乎不变”

这篇论文的价值是把 k-anonymity 的短板讲透，并给出一个工程上能检查、能用旧算法改造的加强约束。读它时要记住一句话：k 管“像谁”，l 管“还能猜出什么”。

核心要点

同质性攻击：小组人数够，秘密不够。类比：抽奖箱里有 4 张票，但全写着同一个名字，摸哪张都一样。 k-anonymity 要求每组至少 k 行；l-diversity 发现，如果敏感列全相同，人数再多也只是把同一个答案重复了 k 次。
背景知识攻击：外部常识会排除候选答案。类比：菜单上有三道菜，但你知道朋友坚决不吃辣，就能把辣菜排掉。论文里的 Umeko 例子就是这样：匿名组里有 heart disease 和 viral infection，但攻击者知道日本人心脏病概率低，于是更确信她是 viral infection。
三种落地定义：从简单到灵活。类比：检查水果篮可以数种类，也可以看比例，还可以允许苹果多一点但不能压倒其他水果。 distinct l-diversity 只数不同敏感值；entropy l-diversity 要求分布足够分散；recursive (c, l)-diversity 允许一定偏斜，更贴近真实数据。

实践案例

案例 1：检查最简单的 distinct l-diversity

groups = {
    "130**|3*|*": ["Cancer", "Cancer", "Cancer", "Cancer"],
    "1485*|40+|*": ["Cancer", "Heart", "Virus", "Virus"],
}
l = 3
for qi, diseases in groups.items():
    ok = len(set(diseases)) >= l
    print(qi, ok)

逐部分解释：

qi 是准标识符泛化后的等价类，比如 ZIP、年龄、国籍
diseases 是这个等价类里的敏感属性
第一组虽然有 4 行，但只有 1 种疾病，所以不满足 l=3

案例 2：用分布看同质性风险

from collections import Counter

def top_share(values):
    counts = Counter(values)
    return max(counts.values()) / len(values)

print(top_share(["AIDS"] * 19 + ["Flu"]))  # 0.95

逐部分解释：

Counter 统计敏感值出现次数
top_share 看最常见敏感值占比
论文实验专门看过 95% 同质小组：哪怕不是 100%，攻击者也会“几乎确信”

案例 3：为什么它还不是差分隐私

def publish_l_diverse(block):
    values = {row["disease"] for row in block}
    if len(values) >= 3:
        return block
    return "generalize more"

print(publish_l_diverse([{"disease": "Cancer"}, {"disease": "Flu"}]))

逐部分解释：

这段逻辑检查的是发布表里每个组是否足够多样
差分隐私检查的是：多一条或少一条个人记录，输出分布是否几乎不变
所以 l-diversity 仍然依赖数据分组和攻击模型；DP 则把保证放在随机算法本身

踩过的坑

把 k 当成 l：k 是组大小，l 是敏感值多样性；组里 20 人全是同一种病仍然危险。
以为 distinct l-diversity 足够：有 3 种值但比例是 98%、1%、1%，攻击者仍能高置信猜多数值。
忘记全局偏斜：如果整个医院 90% 都是某常见病，强行每组均匀会损失大量信息。
拿它当差分隐私替代品：l-diversity 不处理多次发布、组合查询和“我是否在数据里”的邻接数据集保证。

适用 vs 不适用场景

适用：

医疗、人口普查、客户交易这类要发布“个人级表格”的场景
已经在做 k-anonymity，但担心等价类里敏感值太单一
数据发布者知道哪些列是准标识符、哪些列是敏感属性
想用 generalization lattice 和 Incognito 这类算法继续做工程实现

不适用：

需要反复回答统计查询的系统；这类更接近差分隐私或查询审计
攻击者能拿到非常强的个体级背景知识，足以排除几乎所有候选值
敏感属性很多且彼此相关；逐列检查 l-diversity 可能仍然泄露联合信息
要求严格可组合隐私预算的产品级遥测或机器学习训练

历史小故事（可跳过）

2002 年：Latanya Sweeney 用 k-anonymity 把“删除姓名还不够”变成可检查的表格条件。
2005 年前后：Incognito 等算法让 k-anonymity 可以用泛化格搜索来实现，工程入口已经存在。
2006 年：Machanavajjhala 等人在 ICDE 版本中指出 k-anonymity 的同质性攻击和背景知识攻击。
2007 年：TKDD 版本把 l-diversity 的形式化、算法单调性和实验补得更完整。
2007 年之后：t-closeness 继续指出 l-diversity 仍不够，因为局部分布还要接近全局分布。

学到什么

匿名化不是“删掉姓名”，而是要说清楚攻击者能拿什么外部信息来联表。
只保证每组人数足够，会漏掉“组里敏感值太集中”的属性泄露。
l-diversity 的直觉是增加攻击者要排除的候选答案数量；l 越大，攻击者要掌握的排除知识越多。
它比 k-anonymity 强，但仍是发布表约束；差分隐私强在算法级、邻接数据集级、可组合级保证。

关联

sweeney-k-anonymity-2002 —— l-diversity 直接继承并修补 k-anonymity
dwork-dp-icalp-2006 —— 解释为什么匿名化约束不等于差分隐私保证
dwork-calibrating-noise-2006 —— DP 用噪声校准个体影响，而不是检查等价类
dwork-our-data-ourselves-2006 —— 同一年隐私定义路线从“发布表”转向“算法输出”
li-t-closeness-2007 —— 后续工作指出敏感值分布本身也要接近总体
lefevre-incognito-2005 —— 论文实验改造的 k-anonymity 泛化格搜索算法

反向链接

li-t-closeness-2007 —— Li t-closeness 2007 — 用整体分布约束匿名分组

Machanavajjhala l-Diversity 2007 — 给匿名分组补上敏感值多样性

是什么

为什么重要

核心要点

实践案例

案例 1：检查最简单的 distinct l-diversity

案例 2：用分布看同质性风险

案例 3：为什么它还不是差分隐私

踩过的坑

适用 vs 不适用场景

历史小故事（可跳过）

学到什么

延伸阅读

关联

反向链接