Worst-Case Utility Privacy Mechanism via Pointwise Maximal Leakage
This work addresses the underexplored problem of optimizing worst-case utility in privacy mechanisms, which is not feasible with Differential Privacy due to its inability to have zero probabilities.
The paper proposes a discrete privacy mechanism using Pointwise Maximal Leakage (PML) that maximizes worst-case utility while satisfying PML privacy guarantees. The mechanism allows zero conditional probabilities, preventing low utilities, and is shown to be optimal with low computational complexity.
We propose a discrete privacy mechanism exploiting beneficial properties of the novel privacy measure Pointwise Maximal Leakage (PML). Given the utility assignment characterized by every input-output letter pair, we study the mechanism design problem that satisfies PML privacy guarantees and maximizes the worst-case utility. Unlike popular privacy measures like Differential Privacy (DP), PML allows us to set some conditional probabilities in the mechanism to be zero and thereby preventing the occurrence of some low utilities while preserving a strict PML constraint. We show that the utility-safe mechanism, with low computational complexity, is optimal for the worst-case utility problem with an additional constraint on the output support set. We finally demonstrate the effectiveness in several numerical experiments. Due to DP's inability to have zeros in the mechanism, the design of privacy mechanisms that optimize the worst-case utility is underexplored, and this work shows that PML is a privacy measure that is perfectly suited for this purpose.