Utility-Privacy Tradeoffs in Databases: An Information-Theoretic Approach

引言

如图1所示，在合法交易过程中，用户学习一些公共信息（例如，性别和体重），该公共信息被允许并且需要被支持以使交易有意义。他还可以学习/推断私人信息（例如，癌症诊断和收入），这是需要预防（或最小化）的信息。因此，数据的每个用户（可能）也是一个对手。多个研究团体已经研究了隐私和信息泄漏问题数十年。信息理论解决问题的方法很少而且相差很远，并且主要集中在使用信息理论度量上。但是，对效用-隐私（UP）权衡问题的严格的信息理论处理仍然是开放的，以下问题尚待解决：（i）允许进行信息理论分析的数据的统计假设，（ii）向不同的用户显示不同级别的私人信息的能力，以及（iii）对现有知识进行建模和说明。在这项工作中，我们寻求应用信息理论工具来解决提供严格的U-P权衡的分析表征的开放性问题。如果人们将存储库中数据的公共和私有属性视为具有联合概率分布的随机变量，则数据库中的私有属性将保持私有状态，以至于揭示公共属性不会释放有关该属性的其他信息，换句话说，就是将风险降到最低隐私丢失的含义意味着，在公开之后，私有属性的条件熵应尽可能高。因此，在图1中，保持癌症属性私有意味着如果已知性别和体重的公共属性，癌症属性的可预测性应保持不变。为此，已对条目1中的性别属性进行了“消毒”。

数据源的实用性在于其公开数据的能力，因此，隐私考虑可能会损害实用性。实际上，在这种情况下，实用程序和隐私是相互竞争的目标。为了进行合理的权衡，我们需要知道在给定的隐私级别下可实现的最大效用，反之亦然，即，对所有可实现的U-P权衡点的集合进行分析表征。我们表明，可以使用信息理论中的一种精美工具（即速率失真理论）来做到这一点：效用可以通过保真度进行量化，而保真度又与失真相关（成反比）。速率失真必须通过通过熵量化的隐私约束来增加，这与熵有关。

我们的贡献：这项工作的主要贡献是使用速率失真理论和额外的隐私权，精确量化了由数据代表的个人的隐私需求与任何数据源的已清理（已发布）数据的实用性之间的折衷。效用通过失真（准确性）（相反）量化，而通过模棱两可（熵）量化隐私。我们首次通过对披露率的额外限制（即对经过清理的数据的精度进行衡量）来揭示信息披露的基本维度。公共数据的任何受控披露都需要指定披露的准确性和准确性；虽然可以使用数字数据的附加噪声来混合两者，但是附加噪声不是分类数据（社会保险号，邮政编码，疾病状态等）的选项，因此指定输出精度变得很重要。例如，在图1中，权重属性是一个数字字段，可能会因随机加性噪声而失真，也可能会被截断（或量化）为90-100、100-110等范围。识别和保护成绩单中学生隐私的社会安全号码（SSN）是一个熟悉的非数字示例。通过将启发式精度降低到通常的后四位来实现（完整SSN的）消毒。理想的是一个理论框架，它正式规定了实现最佳U-P权衡所必需和足够的输出精度。在[1]中，提出了一种简单源模型的速率失真等效（RDE）权衡。我们将这种形式主义转化为U-P问题，并开发了一个框架，该框架使我们能够建模通用数据源，包括多维数据库和数据流[2]，开发抽象的效用和隐私指标，并量化U-P的基本权衡特征。然后，我们提出一种实现U-P权衡区域的消毒方案，并在数值和分类示例中演示该方案的应用。注意到用户/对手可用的关联可以是内部的（即，数据库内变量之间）或外部的（具有数据库外部但用户/对手可以访问的变量），

我们的示例说明了我们框架的两个基本方面：（i）数据和U-P度量的统计模型如何揭示适当的数据失真和抑制，以实现隐私和效用保证； （ii）了解源统计信息如何确定U-P最佳消毒机制，从而确定最大的U-P权衡区域。本文的结构如下。在第二部分中，我们简要概述了数据库隐私研究的最新状况。在第三节中，我们激发了对信息理论分析的需求，并提出了我们分析框架背后的直觉。在第四节中，我们为结构化数据源（例如数据库）提供了一个抽象模型和度量。我们将在第五节中开发主要的分析框架，

相关工作

K-匿名等所有这些技术已被证明是非通用的，因为它们仅对有限的对手有效。数据库中个人的隐私定义为任何对手准确检测该个人数据是否属于数据库的能力的限制。

DP的概念严格胜于我们基于Shannon熵的隐私定义。但是，我们的模型似乎更直观地可访问，并且适合于不需要严格匿名的许多应用程序域。例如，在许多健康数据库中，个人记录的存在不是秘密，而是个人的疾病状态是秘密。

我们的消毒方法适用于数字数据和分类数据，而DP虽然是非常流行的隐私模型，但似乎仅限于数字数据。此外，基于DP的消毒所造成的效用损失可能很大[13]。已经有一些工作指出由于特定应用程序的隐私机制而导致实用程序的丧失[14]。

更普遍地，一种严格的效用-隐私权衡模型以及一种实现所有最佳点的方法一直是开放的，这是本文的主题。信息理论工具用于隐私和相关问题的使用相对较少。 [1]使用含失真约束的率失真理论分析了一个简单的两变量模型，这是这项工作的主要动机。另外，最近有一些工作将差分隐私保证与Renyi熵[15]和Shannon熵[16]进行比较。

动机和背景知识

信息理论上的数据库隐私方法涉及两个步骤：第一步是数据建模步骤，第二步是推导用于消毒的数学形式主义。在介绍正式模型和抽象之前，我们首先对下面的方法提出一种直观的理解和动力。

动机：统计模型

我们的工作基于以下观察：大型数据集（包括数据库）具有分布基础；即，存在用于数据的基础（有时是隐式）统计模型。即使在只有一个或几个数据集实例可用的数据挖掘情况下，属性之间相关性的使用也会使用关于数据集的隐式分布假设。我们显式地将数据建模为由具有有限或无限字母以及已知分布的源生成的数据。数据库的每一行都是（个人的）相关属性的集合，这些属性属于源的字母，并根据该字母（字母）的出现概率生成。

我们的数据库统计模型还受到以下事实的启发：尽管一个人的属性可能是相关的（例如，图1中的体重和癌症属性之间），但大量个人的记录通常是独立的或弱相关的彼此。因此，我们将数据库建模为无记忆源产生的观察值的集合，该无记忆源的输出是独立且均匀分布的。

我们使用条件熵来量化隐私，直观上，隐私是指保持未明确披露的信息的不确定性。

低概率/高信息样本（异常值）被抑制或严重失真，而高概率（频繁出现）的样本仅被轻微失真。正如我们在续集中正式展示的那样，我们用于分类数据库的方法和解决方案抓住了隐私挑战的关键方面，即抑制高信息（低概率离群样本）并使所有其他信息失真（达到所需的效用/失真级别））

我们建议的清理过程是确定达到所需效用和隐私水平的输出（数据库）统计信息，并确定要干扰哪些输入值以及如何概率干扰它们。由于输出统计取决于消毒过程，因此这里考虑的源模型，从数学上讲，问题减少到找到输入到输出的符号过渡概率。

背景知识：速率失真理论

出于隐私建模的目的，数据库中有关任何个人的属性分为两类：可以公开的公共属性和需要隐藏的私有属性。一个属性可以同时是公共的和私有的。任何人的属性都是相关的；这意味着，如果按原样公开公共属性，则用户可以使用相关模型来推断有关私有属性的信息。因此，确保私有属性（隐藏属性）的私密性要求修改/清除/扭曲公共属性。但是，公共属性具有限制失真的效用约束，

我们的方法是确定最佳清理，即一种映射，该映射在转换数据库的公共属性的所有可能映射的集合中，保证了针对公共属性的期望效用级别的私有属性的最大隐私性。我们使用术语编码和解码分别在数据发布者端和用户端表示此映射。数据库实例是对随机源的实现（当属性数量多时，该源是向量），并且可以被视为维空间中的一个点（参见图2）。可以使用源统计信息（概率分布）生成的所有可能数据库（-length源序列）的集合都位于此空间中。我们选择的效用度量标准是通过失真要求对原始数据库和公开数据库公共属性之间的平均“紧密度”进行度量。因此，消毒的输出将是半径范围内的另一个数据库（同一维空间中的另一个点）。我们试图确定一组输出数据库，其中一个参数的含义将在下面讨论，以“覆盖”该空间，即在给定任何输入数据库实例的情况下