|
The Impact of Range Constraints on Utility in the Design of Differentially Private Mechanisms
William Lee Croft(a),(*), Jörg-Rüdiger Sack(a), Wei Shi(b)
Transactions on Data Privacy 13:3 (2020) 171 - 200
Abstract, PDF
(a) Carleton University, School of Computer Science.
(b) Carleton University, School of Information Technology.
e-mail:leecroft @cmail.carleton.ca; ;
|
|
Abstract
For the design of differentially private mechanisms, knowledge of constraints on query responses can often be leveraged to improve the utility of a mechanism. This is typically considered in the non-interactive setting, where constraints over batches of query responses can be exploited. Comparatively, little attention is given to the design of constraint-adherent mechanisms in the interactive setting, where queries are posed on an individual basis. The absence of relationships between batched responses in the interactive setting removes much of the structure that mechanisms in the non-interactive setting rely on. Yet, if the valid range of a query is known, the design of range-adherent mechanisms remains a possibility. The generation of noisy responses strictly within the valid range of the query can serve to improve the utility of the mechanism. Furthermore, adherence to range constraints is often beneficial for compatibility with downstream software used to analyze the noisy responses.
In this paper, we consider the design of range-adherent mechanisms for general numeric queries in the interactive setting. We first study requirements and desirable properties for range-adherent mechanisms using a matrix representation of discretized probability density functions. We then propose a linear programming approach for the design of range-adherent mechanisms using a user-independent criterion for optimal utility. We run experiments to compare our linear programming mechanisms to other range-adherent alternatives. In these experiments, we measure utility both in terms of the usability of the noisy query responses as well as the information preservation of the mechanisms. The results demonstrate that our linear programming mechanisms achieve higher utility when compared to existing mechanisms. The improvements in utility are most pronounced when there is a high ratio of query sensitivity to query range. Our mechanisms are thus particularly useful for queries posed on small-sized databases which are more vulnerable to privacy breaches.
|
