Sensitivity Analysis for Non-Interactive Differential Privacy: Bounds and Efficient Algorithms
[ X ]
Tarih
2020
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
IEEE Computer Soc
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
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.
Açıklama
Anahtar Kelimeler
Differential privacy, clique problems, statistical database security, SQL, range queries
Kaynak
Ieee Transactions on Dependable and Secure Computing
WoS Q Değeri
Q1
Scopus Q Değeri
Q1
Cilt
17
Sayı
1