Differentially Private Data Releasing for Smooth Queries
Differentially Private Data Releasing for Smooth Queries
复制标题
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Ziteng Wang;Chi Jin;Kai Fan;Jiaqi Zhang;Junliang Huang;Yiqiao Zhong;Liwei Wang
中科院分区：
文献类型：
--
作者：
Ziteng Wang;Chi Jin;Kai Fan;Jiaqi Zhang;Junliang Huang;Yiqiao Zhong;Liwei Wang
在过去的几年里，差异隐私已经成为隐私领域的标准概念。该领域最重要的问题之一是在回答查询的同时保留差异隐私。尽管进行了广泛的研究，但大多数现有的差分隐私查询应答工作都假设数据是离散的（即在 {0; 1}d 中），并且重点关注由布尔函数引发的查询。然而，在实际应用中，连续数据至少与二进制数据一样常见。因此，在这项工作中，我们探索了一个较少研究的主题，即具有连续函数的连续数据的差分私有查询答案。作为走向连续情况的第一步，我们研究了连续数据上的一类自然线性查询，我们将其称为平滑查询。如果线性查询是由 [-1; 上定义的函数指定的），则称该查询是 K 平滑的。 1]d 其直到 K 阶的偏导数都是有界的。我们开发了两种电子差分私有机制，能够回答所有顺利的查询。第一个机制输出数据库的摘要，然后可以给出查询的答案。第二种机制是第一种机制的改进，它输出一个综合数据库。这两种机制都达到了 O(n-K/2d+K/e) 的精度。这里我们假设维度 d 是一个常数。事实证明，即使在这种参数设置下（这在离散情况下几乎是微不足道的），使用现有的离散机制来回答平滑查询也是很困难的，并且需要更多的噪声。我们的机制基于具有一致有界系数的低次偶三角多项式对（变换后的）平滑函数的 L∞ 近似。我们还开发了该机制的实用有效变体，并取得了有希望的实验结果。
In the past few years, differential privacy has become a standard concept in the area of privacy. One of the most important problems in this field is to answer queries while preserving differential privacy. In spite of extensive studies, most existing work on differentially private query answering assumes the data are discrete (i.e., in {0; 1}d) and focuses on queries induced by Boolean functions. In real applications however, continuous data are at least as common as binary data. Thus, in this work we explore a less studied topic, namely, differential privately query answering for continuous data with continuous function. As a first step towards the continuous case, we study a natural class of linear queries on continuous data which we refer to as smooth queries. A linear query is said to be K-smooth if it is specified by a function defined on [-1; 1]d whose partial derivatives up to order K are all bounded. We develop two e-differentially private mechanisms which are able to answer all smooth queries. The first mechanism outputs a summary of the database and can then give answers to the queries. The second mechanism is an improvement of the first one and it outputs a synthetic database. The two mechanisms both achieve an accuracy of O(n-K/2d+K/e). Here we assume that the dimension d is a constant. It turns out that even in this parameter setting (which is almost trivial in the discrete case), using existing discrete mechanisms to answer the smooth queries is difficult and requires more noise. Our mechanisms are based on L∞-approximation of (transformed) smooth functions by low-degree even trigonometric polynomials with uniformly bounded coefficients. We also develop practically efficient variants of the mechanisms with promising experimental results.