Achieving Pareto-Optimal MI-Based Privacy-Utility Tradeoffs Under Full Data
Matthew P. Johnson, Liang Zhao, Supriyo Chakraborty · IEEE Journal of Selected Topics in Signal Processing · 2018
We study a fine-grained model in which a perturbed version of some data ($D$) is to be disclosed, with the aims of permitting the receiver to accurately infer someusefulaspects ($X=f(D)$) of it, while preventing her from inferring otherprivateaspects ($Y=g(D)$). Correlation between the bases for these inferences necessitates compromise between these goals. Determining exactly how the disclosure ($M$) will be probabilistically generated (from$D$), somehow trading off between making$I(M;X)$large and$I(M;Y)$small, is cast as an algorithmic optimization problem. In 2013, Chakrabortyet al.provided optimal solutions for the two extreme points on these objectives’ Pareto frontier: maximizing$I(M;X)$s.t.$I(M;Y)=0$(“perfect privacy,” via linear programming (LP)) and minimizing$I(M;Y)$s.t.$H(X|M)=0$(“perfect utility,” for which the trivial solution$M=X$is optimal). We show that when minimizing$I(M;Y)-\beta I(M;X)$, we can restrict ourselves w.l.o.g. to solutions satisfying several normal-form conditions, which leads to 1) an alternativeconvex programmingformulationwhen$\beta \in [0,1]$, which we provide a practical optimal algorithm for, and 2) proof that$M=X$is actually optimal forall$\beta \geq 1$. This solves the primary open problem posed by Chakrabortyet al.(It also provides a faster solution than Chakrabortyet al.'s LP for the “perfect privacy” special case.)