Preserving Privacy and Fidelity via Ehrhart Theory
Additional Document Info
2018 IEEE. We consider the problem of designing a database sanitization mechanism (DSM) that minimizes, in the expected sense, the mathbb L- 1 -distortion between the histograms of original and sanitized databases, while being -differentially private (DP). The expected mathbb L- 1 -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.
name of conference
2018 IEEE International Symposium on Information Theory (ISIT)