Preserving Privacy and Fidelity via Ehrhart Theory Conference Paper uri icon

abstract

  • © 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)

published proceedings

  • 2018 IEEE International Symposium on Information Theory (ISIT)

author list (cited authors)

  • Padakandla, A., Kumar, P. R., & Szpankowski, W

citation count

  • 3

complete list of authors

  • Padakandla, Arun||Kumar, PR||Szpankowski, Wojciech

publication date

  • June 2018

publisher