传统数据隐私保护技术

数据的隐私保护问题最早由统计学家Dalenius 在20世纪70年代末提出 。他认为保护数据库中的隐私信息，就是要使任何用户 （包括合法用户和潜在的攻击者）在访问数据库的过程中无法获取关于任意个体的确切信息。

一、K-匿名性（K-anonymity）[1]

是一种用于保护隐私的数据匿名化技术。其主要目标是通过对数据集中的个人信息进行处理，防止在发布数据时泄露个体隐私。

在k-匿名性的框架下，数据集中的每一个记录至少与k-1个其他记录在关键属性（如年龄、性别、邮政编码等）上是相同的。这意味着，即使攻击者知道一个人的这些关键属性，他们也无法将该人从k个相似的记录中唯一识别出来。

1. 核心概念

  • 关键属性（Quasi-Identifier）: 这些是可以单独或组合用来识别个体的属性。例如，年龄、性别和邮政编码可以被组合使用来识别一个人。
  • 泛化（Generalization）: 通过将具体值替换为较为宽泛的范围值来实现。例如，将“34岁”泛化为“30-40岁”。
  • 抑制（Suppression）: 直接删除或隐藏某些值来避免泄露。例如，将某些邮政编码用“*”代替。

2. 实现k匿名

为了实现k-匿名性，通常会对数据进行泛化或抑制，使得每个记录都与至少k-1个其他记录无法区分。这样，任何企图通过关键属性识别个体的尝试都将失败。

3. 优缺点

  • 优点:
    • 相对简单且易于理解和实现。
    • 适用于多种类型的数据集。
  • 缺点:
    • 可能会丢失数据的细节，影响数据的实用性。
    • 在数据分布不均匀的情况下，可能难以实现高效的k-匿名性。

二、L-多样性（L-diversity）[2]

是对k-匿名性的进一步改进，旨在解决k-匿名性可能存在的某些弱点，尤其是在应对同质性攻击（homogeneity attack）和背景知识攻击（background knowledge attack）时（在下方介绍）。

1. 核心概念

  1. 敏感属性（Sensitive Attribute）: 这是指那些在匿名化过程中需要特别保护的属性，如医疗记录中的疾病类型、金融数据中的收入信息等。
  2. 多样性要求: 在l-多样性中，每个等价类（quasi-identifier相同的记录组成的类）中，敏感属性至少有l种不同的值。这意味着即使攻击者可以识别出某个等价类中的记录属于某个个体，也无法通过敏感属性确定出个体的具体信息。

2. 实现l-多样性

为了实现l-多样性，在匿名化处理时不仅要确保每个等价类中的记录数不小于k（即满足k-匿名性），还要确保这些记录中的敏感属性具有足够的多样性。具体来说，每个等价类中的敏感属性值的不同种类数目要达到l。

例如，如果在一个数据集中，对某类人群的敏感属性（如疾病类型）进行了匿名化处理，那么为了实现3-多样性，该等价类中必须包含至少3种不同的疾病类型。这就避免了即使知道一个人属于某个等价类，也无法确定他的具体疾病。

3. 解决的问题

l-多样性解决了k-匿名性的一些不足之处。例如：

  • 同质性攻击: 在k-匿名性中，某些等价类可能在敏感属性上具有相同的值，这使得即使数据集匿名化了，攻击者依然能够通过该属性推断出个人的具体信息。而l-多样性通过确保多样性来防止这一问题。
  • 背景知识攻击: 在某些情况下，攻击者可能拥有目标个体的背景知识，并利用这种知识缩小对某个等价类中的敏感属性的推断范围。l-多样性通过增加等价类中敏感属性的多样性，降低了背景知识攻击的成功率。

4. 优缺点

  • 优点:
    • 进一步增强了数据的隐私保护效果，尤其是在敏感属性较为集中的数据集上。
  • 缺点:
    • 实现较为复杂，且在某些数据集中，满足l-多样性的要求可能导致数据实用性降低。
    • 并不能完全消除所有可能的隐私泄露风险。

三、T-邻近性（t-closeness) [3]

是继l-多样性之后提出的又一隐私保护模型，它旨在解决l-多样性的一些局限性，特别是针对敏感属性分布不均导致的隐私泄露问题。

1. 核心概念

  1. 敏感属性分布: 在t-邻近性中，除了关注敏感属性的多样性外，还关注敏感属性的分布情况。t-邻近性要求每个等价类中灵敏属性的分布与整个数据集中的灵敏属性分布足够接近。
  2. 地球移动距离（Earth Mover’s Distance, EMD）: t-邻近性通常使用地球移动距离来衡量等价类中灵敏属性的分布与全局分布之间的差异。EMD是一种用于比较两个分布之间差异的度量方法。

2. 实现t-邻近性

t-邻近性的具体实现是确保每个等价类中敏感属性的分布与整个数据集中的敏感属性分布之间的距离（根据EMD度量*）不超过阈值t。换句话说，如果一个等价类的灵敏属性分布和整体分布非常接近，那么即使攻击者知道某个个体属于该等价类，也无法利用此信息做出有意义的推断。

*Earth Mover’s Distance，地球移动距离。是一种用于度量两个概率分布之间差异的距离度量方法。

3. 解决的问题

t-邻近性解决了k-匿名性和l-多样性的一些不足，特别是在以下方面：

  • 属性分布攻击: 在k-匿名性和l-多样性模型下，如果某个等价类中的敏感属性分布严重偏离整个数据集的分布，攻击者仍然可以通过分析等价类中的分布情况推断出个体的敏感属性。t-邻近性通过限制这种分布的偏差，减少了攻击成功的概率。
  • 背景知识攻击: 与l-多样性类似，t-邻近性也能应对背景知识攻击，但更为严格。通过要求等价类与全局数据集的分布接近，它有效防止了背景知识的利用。

4. 优缺点

  • 优点:
    • t-邻近性在保护数据隐私方面更加严谨，能够防止因敏感属性分布差异导致的隐私泄露。
    • 能够对敏感属性的分布进行细粒度控制，提升数据保护的有效性。
  • 缺点:
    • 实现复杂度较高，计算EMD并确保分布差异不超过t值在大型数据集上可能较为耗时。
    • 可能导致数据实用性进一步降低，因为对分布的严格要求可能需要更多的泛化或抑制。

除了上述比较经典的几种隐私保护技术外，还有 ( α , k ) (\alpha,k) (α,k)-匿名性[4]、 M M M-不变性（M-invariance)[5]等方法。前者是在k-匿名性基础上的进一步扩展，旨在解决可能出现的灵敏属性集中度过高的问题，其要求在每个等价类中，敏感属性的集中度不能超过全局分布的 α \alpha α倍；后者主要针对背景知识攻击和基于时间序列数据的攻击，其要求在多个数据发布中，同一个个体的灵敏属性在各个发布中的状态保持不变，或者说属于一个相对稳定的范围。（几种方法的关系从原文的题目也可以看出来）

差分隐私（Differential Privacy）
通过前面关于相关隐私保护的解释，一个与背景知识无关的隐私保护模型才可能抵抗任何新型的攻击。另外，这些早期的隐私保护模型无法提供一种有效且严格的方法来证明其隐私保护水平，因此当模型参数改变时，无法对隐私保护水平进行定量分析。这个缺点削弱了隐私保护处理结果的可靠性[6]。因此，研究人员试图寻求一种新的、鲁棒性足够好的隐私保护模型，能够在攻击者拥有最大背景知识的条件下抵抗各种形式的攻击。差分隐私的提出使得实现这种设想成为可能。

[1] Sweeney, L. . (2002). K-anonymity: a model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10(05), 557-570.

[2] Machanavajjhala, A., Kifer, D., Gehrke, J., & Venkitasubramaniam, M. (2007). l-diversity: Privacy beyond k-anonymity. Acm transactions on knowledge discovery from data (tkdd), 1(1), 3-es.
[3] Li, N., Li, T., & Venkatasubramanian, S. (2006, April). t-closeness: Privacy beyond k-anonymity and l-diversity. In 2007 IEEE 23rd international conference on data engineering (pp. 106-115). IEEE.

[4] Wong, R. C. W., Li, J., Fu, A. W. C., & Wang, K. (2006, August). (α, k)-anonymity: an enhanced k-anonymity model for privacy preserving data publishing. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 754-759).

[5] **ao, X., & Tao, Y. (2007, June). M-invariance: towards privacy preserving re-publication of dynamic datasets. In Proceedings of the 2007 ACM SIGMOD international conference on Management of data (pp. 689-700).

[6] 熊**, 朱天清, & 王晓峰. (2014). 差分隐私保护及其应用. 计算机学报, 37(1), 101-122.