2.1 计算模型

我们假设存在一个可信的和可信赖的数据提供者，他将个人的数据保存在数据库 $D$ 中，通常由若干 N 行组成。数据库每一行包含单个个体的数据，而隐私目标是同时保护每个个体行，同时允许对整个数据库进行统计分析。

在非交互式或离线的模型中，数据提供者会一次性地生成某种对象，例如“合成数据库”、“摘要统计数据集合”或“净化数据库（经数据清洗的数据库）”。发布后，数据提供者不再扮演任何角色，原始数据可能会被销毁。

查询是应用于数据库的函数。交互式或在线模型允许数据分析员自适应地询问查询，根据观察到的对先前查询的响应来决定下一个查询的位置。

可信的管理员可以被一组个人运行的协议所代替，这些协议使用加密技术来实现安全多方协议。但在大多数情况下，我们对加密假设不感兴趣。第12节描述了这一模型和文献中研究的其他模型。

当所有的查询都提前知道时，非交互模型应该提供最佳的准确性，因为它能够在知道查询结构的情况下关联噪声。相反，当事先不知道有关查询的信息时，非交互式模型会带来严峻的挑战，因为它必须为所有可能的查询提供答案。正如我们将看到的，为了确保隐私，甚至是防止隐私灾难，准确度必然会随着问题的数量而下降，对所有可能的问题提供准确的答案将是不可行的。

差分隐私机制是一种算法，它将一个数据库或一组全体数据类型 $\mathcal{X}$ （所有可能的数据库行）、随机位和一组查询（可选）作为输入，并生成一个输出字符串。希望可以对输出字符串进行解码，以便对查询产生相对准确的答案。如果没有出现任何查询，那么我们就处于非交互式的情况下，希望输出字符串可以被解释为将来的查询提供答案。

在某些情况下，我们可能要求输出字符串是合成数据库。这种合成数据库是由所有可能的数据库行（$\mathcal{X}$）中得到的多集合组成。这种情况下的解码方法是对合成数据库进行查询，然后应用一些简单的变换，如缩放因子的乘法，使其近似于查询的真实答案。