İnan, Ali and Gürsoy, Mehmet Emre and Saygın, Yücel (2020) Sensitivity analysis for non-interactive differential privacy: bounds and efficient algorithms. IEEE Transactions on Dependable and Secure Computing, 17 (1). pp. 194-207. ISSN 1545-5971 (Print) 1941-0018 (Online)
![[thumbnail of IEEETDSC-1.pdf]](https://research.sabanciuniv.edu/style/images/fileicons/application_pdf.png)
IEEETDSC-1.pdf
Restricted to Registered users only
Download (964kB) | Request a copy
Official URL: http://dx.doi.org/10.1109/TDSC.2017.2734664
Abstract
Differential privacy (DP) has gained significant attention lately as the state of the art in privacy protection. It achieves privacy by adding noise to query answers. We study the problem of privately and accurately answering a set of statistical range queries in batch mode (i.e., under non-interactive DP). The noise magnitude in DP depends directly on the sensitivity of a query set, and calculating sensitivity was proven to be NP-hard. Therefore, efficiently bounding the sensitivity of a given query set is still an open research problem. In this work, we propose upper bounds on sensitivity that are tighter than those in previous work. We also propose a formulation to exactly calculate sensitivity for a set of COUNT queries. However, it is impractical to implement these bounds without sophisticated methods. We therefore introduce methods that build a graph model G based on a query set Q, such that implementing the aforementioned bounds can be achieved by solving two well-known clique problems on G. We make use of the literature in solving these clique problems to realize our bounds efficiently. Experimental results show that for query sets with a few hundred queries, it takes only a few seconds to obtain results.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Differential privacy; clique problems; statistical database security; SQL; range queries |
Divisions: | Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng. Faculty of Engineering and Natural Sciences |
Depositing User: | Yücel Saygın |
Date Deposited: | 21 Sep 2020 18:46 |
Last Modified: | 14 Jun 2023 11:51 |
URI: | https://research.sabanciuniv.edu/id/eprint/40552 |