The matrix mechanism: optimizing linear counting queries under differential privacy
The matrix mechanism: optimizing linear counting queries under differential privacy
复制标题
DOI：
10.1007/s00778-015-0398-x
复制
发表时间：
2015-12-01
期刊：
影响因子：
4.2
通讯作者：
Rastogi, Vibhor
中科院分区：
文献类型：
--
作者：
Li, Chao;Miklau, Gerome;Rastogi, Vibhor
差异隐私是一种强大的隐私标准，已成功应用于一系列数据分析任务。我们描述了矩阵机制，这是一种用于回答线性计数查询的工作量的算法，该算法使噪声分布适应于所提供的查询的属性。在给定工作负载的情况下，该机制使用一组不同的查询，称为查询策略，使用标准的拉普拉斯或高斯机制进行回答。然后，从对策略查询的噪声应答中导出对工作负载查询的噪声应答。这两个阶段的过程可能会产生更复杂、相关的噪声分布，既保留了差异隐私，又提高了精度。我们对该机制产生的查询结果的错误进行了形式化分析，并研究了支持给定工作量的最优查询策略的计算问题。我们证明了这个问题可以表示为一个秩受约束的半定规划。我们分析了文献中提出的两种看似截然不同的技术，通过将它们视为矩阵机制的实例来解释它们相似的行为。我们还描述了一个扩展的机制，其中非负约束包括在推导过程中，并提供了其有效性的实验证据。
Differential privacy is a robust privacy standard that has been successfully applied to a range of data analysis tasks. We describe the matrix mechanism, an algorithm for answering a workload of linear counting queries that adapts the noise distribution to properties of the provided queries. Given a workload, the mechanism uses a different set of queries, called a query strategy, which are answered using a standard Laplace or Gaussian mechanism. Noisy answers to the workload queries are then derived from the noisy answers to the strategy queries. This two-stage process can result in a more complex, correlated noise distribution that preserves differential privacy but increases accuracy. We provide a formal analysis of the error of query answers produced by the mechanism and investigate the problem of computing the optimal query strategy in support of a given workload. We show that this problem can be formulated as a rank-constrained semidefinite program. We analyze two seemingly distinct techniques proposed in the literature, whose similar behavior is explained by viewing them as instances of the matrix mechanism. We also describe an extension of the mechanism in which nonnegativity constraints are included in the derivation process and provide experimental evidence of its efficacy.