Metric Differential Privacy at the User-Level
arxiv(2024)
摘要
Metric differential privacy (DP) provides heterogeneous privacy guarantees
based on a distance between the pair of inputs. It is a widely popular notion
of privacy since it captures the natural privacy semantics for many
applications (such as, for location data) and results in better utility than
standard DP. However, prior work in metric DP has primarily focused on the
item-level setting where every user only reports a single data item. A
more realistic setting is that of user-level DP where each user contributes
multiple items and privacy is then desired at the granularity of the user's
entire contribution. In this paper, we initiate the study of metric DP
at the user-level. Specifically, we use the earth-mover's distance
(d_) as our metric to obtain a notion of privacy as it captures
both the magnitude and spatial aspects of changes in a user's data.
We make three main technical contributions. First, we design two novel
mechanisms under d_-DP to answer linear queries and item-wise
queries. Specifically, our analysis for the latter involves a generalization of
the privacy amplification by shuffling result which may be of independent
interest. Second, we provide a black-box reduction from the general unbounded
to bounded d_-DP (size of the dataset is fixed and public) with a
novel sampling based mechanism. Third, we show that our proposed mechanisms can
provably provide improved utility over user-level DP, for certain types of
linear queries and frequency estimation.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要