2013/12/02 by Quan Geng, Pramod Viswanath, Geng, Quan +1
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1312.0655
openalex publication_date 2013/12/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We derive the optimal ε-differentially private mechanism for a general two-dimensional real-valued (histogram-like) query function under a utility-maximization (or cost-minimization) framework for the ℓ1 cost function. We show that the optimal noise probability distribution has a correlated multidimensional staircase-shaped probability density function. Compared with the Laplacian mechanism, we show that in the high privacy regime (as ε→ 0), the Laplacian mechanism is approximately optimal; and in the low privacy regime (as ε→ +∞), the optimal cost is Θ(e^-\fracε3), while the cost of the Laplacian mechanism is \frac2Δε, where Δ is the sensitivity of the query function. We conclude that the gain is more pronounced in the low privacy regime. We conjecture that the optimality of the staircase mechanism holds for vector-valued (histogram-like) query functions with arbitrary dimension, and holds for many other classes of cost functions as well.