Paper Info
Title
Preserving Privacy and Fidelity via Ehrhart Theory
Abstract
We consider the problem of designing a database sanitization mechanism (DSM) that minimizes, in the expected sense, the L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -distortion between the histograms of original and sanitized databases, while being θ-differentially private (DP). The expected L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -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.
Year
DOI
Venue
2018
10.1109/ISIT.2018.8437778
2018 IEEE International Symposium on Information Theory (ISIT)
Keywords
Field
DocType
Ehrhart theory,database sanitization mechanism,histograms,sanitized databases,LP theory,privacy preservation,utility-privacy trade-off,optimal θ-DP DSM,complex linear program
Analytic combinatorics,Discrete mathematics,Histogram,Combinatorics,Fidelity,Computer science,Linear programming,Distortion
Conference
ISBN
Citations 
PageRank 
978-1-5386-4102-6
1
0.35
References 
Authors
0
3
Name
Order
Citations
PageRank
Arun Padakandla1347.76
P. R. Kumar271771067.24
Wojciech Szpankowski31557192.33