A Graph Symmetrisation Bound on Channel Information Leakage under Blowfish Privacy
This work addresses privacy loss quantification for flexible privacy policies in computer science, representing an incremental advance in connecting differential privacy variants to information-theoretic measures.
The paper tackles the problem of bounding information leakage for Blowfish privacy, a generalization of differential privacy, by relating it to min-entropy leakage from communications theory. It achieves a tight bound using graph symmetrisation, with a construction demonstrating asymptotic equality.
Blowfish privacy is a recent generalisation of differential privacy that enables improved utility while maintaining privacy policies with semantic guarantees, a factor that has driven the popularity of differential privacy in computer science. This paper relates Blowfish privacy to an important measure of privacy loss of information channels from the communications theory community: min-entropy leakage. Symmetry in an input data neighbouring relation is central to known connections between differential privacy and min-entropy leakage. But while differential privacy exhibits strong symmetry, Blowfish neighbouring relations correspond to arbitrary simple graphs owing to the framework's flexible privacy policies. To bound the min-entropy leakage of Blowfish-private mechanisms we organise our analysis over symmetrical partitions corresponding to orbits of graph automorphism groups. A construction meeting our bound with asymptotic equality demonstrates tightness.