Preserving Privacy and Fidelity via Ehrhart Theory

We consider the problem of designing a database sanitization mechanism (DSM) that minimizes, in the expected sense, the L1-distortion between the histograms of original and sanitized databases, while being θ-differentially private (DP). The expected L1-distortion of a corresponding optimal θ-DP DSM provides for an important utility-privacy trade-off. This problem reduces to a prohibitively complex linear program (LP). Using tools from Ehrhart theory, analytic combinatorics and LP theory, we solve this problem and thereby provide a simple closed form computable expression characterizing this trade-off.