期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 62, 期 2, 页码 952-969出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2015.2504972
关键词
Data privacy; randomized algorithm
资金
- National Science Foundation [CCF-1422278]
- University of Illinois at Urbana-Champaign
We study the (nearly) optimal mechanisms in (epsilon, delta)-differential privacy for integer-valued query functions and vector-valued (histogram-like) query functions under a utility-maximization/cost-minimization framework. Within the classes of mechanisms oblivious of the database and the queries beyond the global sensitivity, we characterize the tradeoff between epsilon and delta in utility and privacy analysis for histogram-like query functions, and show that the (epsilon, delta)-differential privacy is a framework not much more general than the (epsilon, 0)-differential privacy and (0, delta)-differential privacy in the context of l(1) and l(2) cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of l(1) and l(2) cost functions, we show the near-optimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as (epsilon, delta) -> (0, 0)). We conclude that in (epsilon, delta)-differential privacy, the optimal noise magnitude and the noise power are Theta(min((1/epsilon), (1/delta))) and Theta(min((1/epsilon(2)), (1/delta(2)))), respectively, in the high privacy regime.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据