20 20

Transactions on
Data Privacy
Foundations and Technologies


Articles in Press

Accepted articles here

Latest Issues

Year 2023

Volume 16 Issue 3
Volume 16 Issue 2
Volume 16 Issue 1

Year 2022

Volume 15 Issue 3
Volume 15 Issue 2
Volume 15 Issue 1

Year 2021

Volume 14 Issue 3
Volume 14 Issue 2
Volume 14 Issue 1

Year 2020

Volume 13 Issue 3
Volume 13 Issue 2
Volume 13 Issue 1

Year 2019

Volume 12 Issue 3
Volume 12 Issue 2
Volume 12 Issue 1

Year 2018

Volume 11 Issue 3
Volume 11 Issue 2
Volume 11 Issue 1

Year 2017

Volume 10 Issue 3
Volume 10 Issue 2
Volume 10 Issue 1

Year 2016

Volume 9 Issue 3
Volume 9 Issue 2
Volume 9 Issue 1

Year 2015

Volume 8 Issue 3
Volume 8 Issue 2
Volume 8 Issue 1

Year 2014

Volume 7 Issue 3
Volume 7 Issue 2
Volume 7 Issue 1

Year 2013

Volume 6 Issue 3
Volume 6 Issue 2
Volume 6 Issue 1

Year 2012

Volume 5 Issue 3
Volume 5 Issue 2
Volume 5 Issue 1

Year 2011

Volume 4 Issue 3
Volume 4 Issue 2
Volume 4 Issue 1

Year 2010

Volume 3 Issue 3
Volume 3 Issue 2
Volume 3 Issue 1

Year 2009

Volume 2 Issue 3
Volume 2 Issue 2
Volume 2 Issue 1

Year 2008

Volume 1 Issue 3
Volume 1 Issue 2
Volume 1 Issue 1

Volume 13 Issue 3

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; ;


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.

* Corresponding author.

Follow us


ISSN: 1888-5063; ISSN (Digital): 2013-1631; D.L.:B-11873-2008; Web Site: http://www.tdp.cat/
Contact: Transactions on Data Privacy; Vicenç Torra; U. of Skövde; PO Box 408; 54128 Skövde; (Sweden); e-mail:tdp@tdp.cat
Note: TDP's web site does not use cookies. TDP does not keep information neither on IP addresses nor browsers. For the privacy policy access here.


Vicenç Torra, Last modified: 08 : 09 December 30 2020.