The Optimal Differential Privacy Mechanism under Hamming Distortion for Universal Memoryless Source Classes.
Kousha Kalantari, Lalitha Sankar, Anand D. Sarwate · arXiv (Cornell University) · 2016
To be considered for the 2016 IEEE Jack Keil Wolf ISIT Student Paper Award. We develop the tradeoff between privacy, quantified using local differential privacy (L-DP), and utility, quantified using Hamming distortion, for specific classes of universal memoryless finite-alphabet sources. In particular, for the class of permutation invariant sources (i.e., sources whose distributions are invariant under permutations), the optimal L-DP mechanism is obtained. On the other hand, for the class of sources with ordered statistics (i.e., for every distribution $P=(P_1,P_2,...,P_M) \in \mathcal{P}, P_1 \ge P_2 \ge P_3 \ge \ldots \ge P_M$), upper and lower bounds on the achievable local differential privacy are derived with optimality results for specific range of distortions.