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

[ X ]

Tarih

2020

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

Künye