l-多样性 — k-匿名之后的隐私保护

是什么

l-多样性（l-diversity）是一种数据发布隐私保护方法：在 k-匿名的基础上，要求每个等价组里的敏感属性值至少有 l 个”充分不同”的种类，让攻击者即使找到了你所在的那个组，也无法高置信度猜出你的具体敏感信息。

类比：你住在一栋有 100 个人的楼（k=100）——k-匿名保证外人不知道你住在哪个房间。但如果这 100 人里 99 人全都患了艾滋病，攻击者翻到这栋楼，立刻知道你十有八九也有。l-diversity 要求这 100 人的病种至少散布在 l 种以上，让猜测变得不可靠。

k-anonymity 解决的是”谁”的问题（身份无法唯一定位），但没解决”什么”的问题（敏感值分布均不均）。Machanavajjhala 等人在 2006 年 ICDE、2007 年 ACM TKDD 上指出这一盲区，并给出三种递进强度的”充分不同”定义：

distinct l-diversity：组内至少有 l 个不同敏感值（最基础，最容易被绕过）
entropy l-diversity：敏感值的信息熵 ≥ log(l)，防止一种值”占统治地位”
recursive (c,l)-diversity：最常见值的出现次数＜ c × 其余所有值出现次数之和，防止”稀有但危险”的值被排除法锁定

为什么重要

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

为什么医院发布的”脱敏数据”有时被反向推出病患身份——只满足了 k-匿名却没做敏感属性多样化
为什么 k-匿名在特殊人群（罕见病、极端收入）上几乎无效——等价组本身就是同质的
为什么差分隐私（differential privacy）最终取代了这一类方案——DP 提供与攻击者无关的数学边界，l-diversity 不提供
为什么数据匿名化有一条无法绕开的根本矛盾：保护越强 → 泛化越激烈 → 数据可用性越低

核心要点

1. k-匿名的两个致命弱点

k-anonymity 只保证你在等价组里”不唯一”，但没有限制组内的敏感属性分布。 同质性攻击：如果一个组的所有 k 条记录敏感值都是”糖尿病”，攻击者看到你所在的组就直接知道你的病情。 背景知识攻击：攻击者若已知某人不可能患”心脏病”，从等价组里排除一种后，剩下的种类可能只有一种——推断同样成立。

2. l-diversity 如何修补：强制敏感属性多样

l-diversity 在 q*-block（等价组：quasi-identifier 泛化到相同值的记录集合）上加约束：每个等价组必须包含至少 l 个”充分表示”的不同敏感值。三种定义里最实用的是 entropy l-diversity：每个组的 H(group) ≥ log(l)，确保攻击者对敏感值的不确定性不低于”l 等可能随机猜”的难度。类比：如果一个抽奖箱至少有 l 种奖品且分布均匀，你的猜中概率上限就是 1/l。

3. 算法：已有的 k-anonymity 算法直接可扩展

l-diversity 不是推倒重来，而是在泛化操作里加一个额外约束：泛化时检查每个新生等价组是否满足 l-diversity；不满足则继续泛化（合并更大的组）。论文证明 Samarati 等人的 k-anonymity 算法只需加这一个循环条件就能适配，已有实现几乎零迁移成本。

实践案例

案例 1：医疗数据脱敏发布

医院要公开患者统计数据，quasi-identifier 为年龄段 + 性别 + 邮编前缀，敏感属性为诊断病种。

import math
from collections import Counter

def check_entropy_l_diversity(group_records, sensitive_col, l):
    """检查一个等价组是否满足 entropy l-diversity"""
    counts = Counter(r[sensitive_col] for r in group_records)
    total = sum(counts.values())
    entropy = -sum((c / total) * math.log(c / total) for c in counts.values())
    return entropy >= math.log(l)

def anonymize_patients(records, l=3):
    from itertools import groupby
    key = lambda r: (r["age_range"], r["gender"], r["zip3"])
    groups = {k: list(v) for k, v in groupby(sorted(records, key=key), key=key)}

    violations = [gid for gid, grp in groups.items()
                  if not check_entropy_l_diversity(grp, "diagnosis", l)]
    print(f"不满足 {l}-diversity 的等价组：{len(violations)} / {len(groups)}")
    return violations

违规的组需要进一步泛化（如把邮编从 3 位缩为 2 位）再重新检查，直到所有组都满足条件。

案例 2：比较 l-diversity 与差分隐私的取舍

两种方案面向不同发布场景：

# l-diversity：发布完整的脱敏行级表（适合 one-shot 公开数据集）
# 保留完整记录，下游可做回归分析；但安全保证依赖攻击者背景知识假设
anonymized_df = apply_l_diversity(
    df, quasi_ids=["age_range", "zip", "gender"],
    sensitive="salary_bracket", l=3
)
anonymized_df.to_csv("public_dataset.csv")   # 行级别数据出门

# 差分隐私：只发布聚合统计值（适合持续查询接口）
# 行级别数据不出门；安全保证来自数学证明，与攻击者背景知识无关
from diffprivlib import tools as dp
mean_salary = dp.mean(df["salary"], epsilon=0.5, bounds=(0, 500_000))
print(f"ε-DP 平均工资：{mean_salary:.0f}")   # 只发一个数字

l-diversity 保留了行级别语义（可以做个体级别分析），代价是安全保证的边界模糊。差分隐私的边界由数学保证，但牺牲了行级别可访问性。

案例 3：政府人口普查微数据发布

政府发布人口普查数据，研究者要做个体级别收入分析：

def generalize_age(age, granularity=10):
    lo = (age // granularity) * granularity
    return f"{lo}-{lo + granularity - 1}"

def anonymize_census(records, sensitive="income_bracket", l=3, max_rounds=6):
    granularity = 5   # 从 5 岁区间开始
    for _ in range(max_rounds):
        for r in records:
            r["age_range"] = generalize_age(r["age"], granularity)
        key = lambda r: (r["age_range"], r["gender"], r["region"])
        groups = group_by(records, key)
        if all(check_entropy_l_diversity(g, sensitive, l) for g in groups.values()):
            return [drop_key(r, "age") for r in records]
        granularity *= 2   # 粒度加粗，扩大等价组
    return None   # 无法在给定轮数内满足

关键规律：l 越大，粒度翻倍次数越多，最终”年龄范围”可能横跨几十岁，年龄字段基本失效——这是数据可用性与隐私强度之间的根本权衡。

踩过的坑

distinct l-diversity 对分布倾斜的属性几乎无效：等价组里有 5 种病但 4 种都是”健康”，1 种是”艾滋病”，攻击者仍以 80% 置信度推断你”健康”——敏感值种类够多，但分布极度不均。entropy l-diversity 才能堵住这个洞。
l 越大，数据越脏：凑齐 l 种敏感值就要不断扩大等价组；l=5 时可能把 30-35 岁和 70-75 岁合并，年龄字段彻底失效。实验显示 l=2 时 UCI Adult 数据集上分类精度已有明显下降。
多敏感属性场景下急剧退化：每列各自满足 l-diversity，不保证联合分布也多样。Aggarwal & Yu 2008 指出：敏感属性列数一多，想让联合分布满足 l-diversity 几乎必须把整个数据集泛化成一个大组——维度灾难。
安全保证依赖对攻击者的假设，不提供数学边界：只要攻击者获得额外背景知识（如”已知该人不患 X”），l-diversity 的保护立即部分失效。这与 ε-差分隐私的可证明数学界有本质区别——DP 对任何攻击者都成立，l-diversity 只对”假设无背景知识”的攻击者成立。

适用 vs 不适用场景

适用：

需要发布可读的行级别脱敏表（研究用医疗数据集、人口普查微数据）
下游需要做个体级别分析、回归建模，而非仅消费聚合统计
团队对”等价组”语义熟悉，需要对监管机构演示可解释的隐私保证
数据集的 quasi-identifier 维数低（≤5），泛化代价可控

不适用：

需要应对持续查询、组合攻击——ε-差分隐私才是正确选择
敏感属性维数高（多列敏感字段）——维度灾难使 l-diversity 代价极高
攻击者背景知识强或无法假设上限——安全保证立即崩溃
数据分布高度倾斜（罕见病数据，99% 同一诊断）——l 再大也无法解决根本的分布问题

历史小故事（可跳过）

1998 年：Samarati & Sweeney 在哈佛发现，通过投票记录（公开）与医院脱敏数据交叉匹配可识别出马萨诸塞州州长的病历，由此提出 k-anonymity，迅速成为数据发布隐私的事实标准。
2002 年：Sweeney 在 IJUFKS 发表 k-anonymity 完整形式化，政府和医疗机构开始大规模采用。
2006 年：Machanavajjhala、Gehrke、Kifer、Venkitasubramaniam（康奈尔大学）在 ICDE 指出 k-anonymity 的同质性攻击与背景知识攻击，提出 l-diversity，开创了”超越 k-anonymity”的研究范式。
2007 年：ACM TKDD 发表完整版。同年 Li et al. 提出 t-closeness，修补 l-diversity 对倾斜分布的不足——从提出到被补丁，只用了一年。
2006-2008 年：Dwork 等人正式提出差分隐私，从根本上绕开了”设计攻击模型”的困境。从此”匿名化研究”与”差分隐私研究”分道而行，后者成为学界和工业界的主流。

学到什么

保护身份 ≠ 保护内容：k-匿名让你在人群里找不到”你”，但如果人群本身是同质的，找到人群就等于找到了你的秘密——l-diversity 修的正是这个逻辑漏洞
安全保证强度 = 对攻击者假设的逆：假设攻击者越弱，保证越强；差分隐私的突破在于把对攻击者的假设降为零，只要 ε 足够小，任何背景知识都防住
隐私与可用性存在信息论层面的根本矛盾：泛化越激烈数据越脏，这不是工程问题，是不可绕过的边界——没有免费午餐
k-anonymity → l-diversity → t-closeness → DP 这条演进线展示了安全研究的典型节奏：发现漏洞 → 局部修补 → 发现新漏洞 → 直到找到了问题的正确抽象

关联

dwork-calibrating-noise-2006 —— 差分隐私通过加噪声彻底绕开”攻击者背景知识”假设，是 l-diversity 所在范式的终结者
dwork-dp-icalp-2006 —— ε-DP 完整形式化，提供 l-diversity 永远给不了的可组合数学保证
codd-1970 —— 关系模型定义了”等价组”的底层数据语义：q*-block 本质上是关系代数的 SELECT + GROUP BY 结果
aes —— 与 l-diversity 同属隐私保护工具箱：AES 保护传输中的数据，l-diversity 保护发布后的静态数据
cryptoverif-2008 —— 形式化密码学验证工具；l-diversity 的”等价组”语义恰好无法用 CryptoVerif 的密码学模型表达，说明它不属于密码学意义上的安全

反向链接

codd-1970 —— Codd 1970 — 关系模型奠基
cryptoverif-2008 —— CryptoVerif — 让计算机直接证密码协议在真实计算模型下安全
dwork-calibrating-noise-2006 —— 校准噪声与敏感度 — Laplace 机制奠基
dwork-dp-icalp-2006 —— 差分隐私 — ε 与邻接数据集不可区分