Key points are not available for this paper at this time.
发布有关包含敏感数据的统计数据库的信息的机制必须在效用和隐私之间找到权衡。发布完全准确的信息可以最大化效用，但会最小化隐私，而发布随机噪声则达成相反的效果。隐私可以通过差分隐私的框架进行严格量化，该框架要求机制的输出分布在给定数据库行被包含或排除时几乎相同。本文的目标是在满足差分隐私的前提下，提供强大且一般的效用保证。我们追求的机制保障对每个潜在用户几乎最优的效用，与其副信息（建模为查询结果的先验分布）和偏好（通过损失函数建模）无关。我们的主要结果是：对于每个固定的计数查询和差分隐私水平，存在一个几何机制 M*——即简单且经过充分研究的拉普拉斯机制的离散变体——它在满足差分隐私约束的情况下，对每个可能用户的期望损失都进行最小化。这是一个极其强大的效用保证：每个潜在用户 u，无论其副信息和偏好如何，从 M* 中获得的效用与与一个针对 u 优化的差分隐私机制 Mu 的交互所获得的效用相同。更准确地说，对于每个用户 u，都存在一个最优机制 Mu，它分为独立于用户的部分（几何机制 M*），后面跟着可以委托给用户自身的特定于用户的后处理。我们这项结果证明的第一部分将固定但任意用户的最优差分隐私机制表征为线性程序中某种基本可行解的形式，该程序的约束编码了差分隐私。第二部分则表明，该多面体的所有相关顶点（涵盖所有可能的用户）都可以通过对几何机制范围的适当重映射推导出来.
Ghosh et al. (Sun,) 研究了这个问题。