The Optimal Mechanism in Differential Privacy
Quan Geng, and Pramod Viswanath Coordinated Science Laboratory and Dept. of ECE University of Illinois, Urbana-Champaign, IL 61801 Email: {geng5,
Abstract
Differential privacy is a framework to quantify to what extent individual privacy in a statistical database is preserved while releasing useful aggregate information about the database. In this work we study the fundamental tradeoff between privacy and utility in differential privacy. We derive the optimal $\epsilon$ -differentially private mechanism for single real-valued query function under a very general utility-maximization (or cost-minimization) framework. The class of noise probability distributions in the optimal mechanism has staircase-shaped probability density functions which are symmetric (around the origin), monotonically decreasing and geometrically decaying. The staircase mechanism can be viewed as a geometric mixture of uniform probability distributions, providing a simple algorithmic description for the mechanism. Furthermore, the staircase mechanism naturally generalizes to discrete query output settings as well as more abstract settings. We explicitly derive the parameter of the optimal staircase mechanism for $\ell_{1}$ and $\ell_{2}$ cost functions. Comparing the optimal performances with those of the usual Laplacian mechanism, we show that in the high privacy
中文速览
差分隐私（differential privacy）要求在发布数据库统计查询结果时，任意一条个人记录的存在与否都不会对输出分布产生显著影响，但如何在满足隐私约束的同时尽量保留数据效用，始终是核心难题。本文针对单个实值查询函数，在一个非常通用的效用最大化（或代价最小化）框架下，严格推导出最优的 ε-差分隐私噪声机制：最优噪声的概率密度函数呈"阶梯形"——关于原点对称、单调递减、几何衰减，可视为若干均匀分布的几何混合，并由此提出"阶梯机制"（staircase mechanism）。将其与广泛使用的拉普拉斯机制（Laplacian mechanism）对比后发现，在高隐私需求（ε 较小）时两者渐近等价，但在低隐私需求（ε 较大）时阶梯机制的噪声幅度和功率仅为指数量级，而拉普拉斯机制的对应量仅以多项式速率下降，差距十分显著。这一结果不仅从理论上回答了"独立于查询输出的扰动是否最优"以及"拉普拉斯噪声是否最优"这两个基本问题，也为实际系统在中低隐私需求场景下设计更高效的隐私保护机制提供了明确的理论依据。
原文 arXiv:1212.1186;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1212.1186v3