Sensitivity Analysis for Non-Interactive Differential Privacy: Bounds and Efficient Algorithms

Basit Öğe Kaydı
dc.authoridInan, Ali/0000-0002-3149-1565
dc.contributor.authorInan, Ali
dc.contributor.authorGursoy, Mehmet Emre
dc.contributor.authorSaygin, Yucel
dc.date.accessioned2025-01-06T17:37:29Z
dc.date.available2025-01-06T17:37:29Z
dc.date.issued2020
dc.description.abstractDifferential 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.
dc.description.sponsorshipScientific and Technological Research Council of Turkey (TUBITAK) [114E261]
dc.description.sponsorshipThis research was funded by The Scientific and Technological Research Council of Turkey (TUBITAK) under grant number 114E261. This manuscript extends previous work presented at the 28th International Conference on Scientific and Statistical Database Management (SSDBM'16).
dc.identifier.doi10.1109/TDSC.2017.2734664
dc.identifier.endpage207
dc.identifier.issn1545-5971
dc.identifier.issn1941-0018
dc.identifier.issue1
dc.identifier.scopus2-s2.0-85028910018
dc.identifier.scopusqualityQ1
dc.identifier.startpage194
dc.identifier.urihttps://doi.org/10.1109/TDSC.2017.2734664
dc.identifier.urihttps://hdl.handle.net/20.500.14669/2234
dc.identifier.volume17
dc.identifier.wosWOS:000535700500013
dc.identifier.wosqualityQ1
dc.indekslendigikaynakWeb of Science
dc.indekslendigikaynakScopus
dc.language.isoen
dc.publisherIEEE Computer Soc
dc.relation.ispartofIeee Transactions on Dependable and Secure Computing
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı
dc.rightsinfo:eu-repo/semantics/closedAccess
dc.snmzKA_20241211
dc.subjectDifferential privacy
dc.subjectclique problems
dc.subjectstatistical database security
dc.subjectSQL
dc.subjectrange queries
dc.titleSensitivity Analysis for Non-Interactive Differential Privacy: Bounds and Efficient Algorithms
dc.typeArticle

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu