似是而非的否认性限制与模型提取导向的k-匿名数据发布

### 似是而非的否认性限制与模型提取导向的k - 匿名数据发布 #### 1. 似是而非的否认性限制 似是而非的否认性（plausible deniability）直观上确保至少有 `thres - 1` 个种子以相似的概率生成记录 `r`。这里给出可测试性的定义：若存在算法 `Test(r, d, γ, par, thres, D)`，当 `r`（以 `d` 为种子）满足 `(thres, γ)` - 似是而非的否认性（PD）时输出 `True`，否则输出 `False`，则称匿名化算法 `Anon` 是可测试的。 ##### 1.1 重新识别的含义 原定义主要关注单个匿名记录 `r` 的安全性，但实际应用中应考虑匿名记录的集合。重新识别的定义如下：设 `D` 为原始数据集，`Anon` 为匿名化算法，`R ⊆ R◦`（其中 `R◦ = {r = Anon(par, d) | d ∈ D}`）。若 `H(d | r, D, R, par) = 0`（`H` 为熵函数，将 `r`、`d`、`D`、`R` 和 `par` 视为随机变量），则称匿名记录 `r = Anon(par, d)`（`r ∈ R` 且 `d ∈ D`）是可重新识别的，即不具有否认性。直观而言，给定 `r`、`par`、`D` 和 `R` 时，原始记录 `d` 的熵为零，这里假设攻击者对原始数据集 `D` 和参数 `par` 有完全的了解。 下面通过一个简单的示例说明：考虑由三个非匿名记录组成的数据集 `D = {d1, d2, d3}`，匿名记录由以下概率分布生成： - 若 `i = 1`，`Pr[Anon(par, di) = rj] = 1/2`，`j = 1, 2`； - 若 `i = 2`，`Pr[Anon(par, di) = rj] = 1/2`，`j = 2, 3`； - 若 `i = 3`，`Pr[Anon(par, di) = rj] = 1/2`，`j = 1, 3`。 可能的匿名数据集如下： | 原始数据集 | 匿名数据集 1 | 匿名数据集 2 | 匿名数据集 3 | | ---- | ---- | ---- | ---- | | d1 | r1 | r2 | r1 | | d2 | r3 | r2 | r2 | | d3 | r3 | r1 | r3 | 显然，这些匿名记录满足 `(2, 1)` - 似是而非的否认性。但如果同时发布这三个记录，某些记录的似是而非的否认性就会受到质疑。例如，若 `(d1, d2, d3)` 被匿名化为 `(r2, r2, r1)`，由于 `Pr[Anon(par, d1) = r2] = 1/2`，`Pr[Anon(par, d2) = r2] = 1/2`，`Pr[Anon(par, d3) = r2] = 0`，且有两个 `r2`，攻击者可以推断出 `r3` 的种子是 `d3`，即 `r3` 不具有否认性，这种情况下失去否认性的概率为 `1/2 × 1/2 × 1/2 = 1/8`，并非小概率事件。 ##### 1.2 贪心消除攻击 为了推广上述示例中的算法，定义 `range(par, D) = {r | Pr[r = Anon(par, d)] > 0 ∧ d ∈ D}`，即所有可能的匿名记录集合。同时定义谓词算法 `Pred`：`Pred : PAR × D × range(par, D) → {True, False}`，当 `Pr[Anon(par, d) = r] > 0` 时，`Pred(par, d, r) = True`，否则为 `False`，其中 `PAR` 是所有可能参数的集合。 贪心消除攻击算法如下： 1. **初始化**：`G ← ∅`，`D′ ← D`，`R′ ← R`； 2. **循环消除**：当存在 `r ∈ R′` 使得 `nR′(r) = |D′coll(r)|` 时（`nR′(r)`