Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy

DOI10.1145/2699501MaRDI QIDQ5012532zbMATH OpenOpenAlexFDO

Authors Ganzhao Yuan, Zhenjie Zhang, Marianne Winslett, Xiaokui Xiao, Yin Yang, Zhifeng Hao

Publication date 25 November 2021

Published in ACM Transactions on Database Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.07526, https://hdl.handle.net/10356/81387

zbMATH Keywords

augmented Lagrangian multiplier algorithmdifferential privacylinear counting querylow rankmatrix approximation

Mathematics Subject Classification ID

Privacy of data (68P27)

Abstract: Differential privacy is a promising privacy-preserving paradigm for statistical query processing over sensitive data. It works by injecting random noise into each query result, such that it is provably hard for the adversary to infer the presence or absence of any individual record from the published noisy results. The main objective in differentially private query processing is to maximize the accuracy of the query results, while satisfying the privacy guarantees. Previous work, notably cite{LHR+10}, has suggested that with an appropriate strategy, processing a batch of correlated queries as a whole achieves considerably higher accuracy than answering them individually. However, to our knowledge there is currently no practical solution to find such a strategy for an arbitrary query batch; existing methods either return strategies of poor quality (often worse than naive methods) or require prohibitively expensive computations for even moderately large domains. Motivated by this, we propose low-rank mechanism (LRM), the first practical differentially private technique for answering batch linear queries with high accuracy. LRM works for both exact (i.e., $epsilon$-) and approximate (i.e., ($epsilon$, $delta$)-) differential privacy definitions. We derive the utility guarantees of LRM, and provide guidance on how to set the privacy parameters given the user's utility expectation. Extensive experiments using real data demonstrate that our proposed method consistently outperforms state-of-the-art query processing solutions under differential privacy, by large margins.

Recommendations

• Near-optimal differentially private mechanism for linear queries
• Differential privacy and the fat-shattering dimension of linear queries
• Unconditional differentially private mechanisms for linear queries
• Privacy-preserving linear and nonlinear approximation via linear programming
• Pure differential privacy for rectangle queries via private partitions
• Topics in Cryptology – CT-RSA 2005
• Lower bounds on the error of query sets under the differentially-private matrix mechanism
• Differentially private data releasing for smooth queries

Cited in

(7)

• Correlated tuple data release via differential privacy
• The optimal upper bound of the number of queries for Laplace mechanism under differential privacy
• Lower bounds on the error of query sets under the differentially-private matrix mechanism
• Answering n^2+o(1) counting queries with differential privacy is hard
• A Linear-Time Multivariate Micro-aggregation for Privacy Protection in Uniform Very Large Data Sets
• Make Up Your Mind: The Price of Online Queries in Differential Privacy
• Towards Instance-Optimal Private Query Release

This page was built for publication: Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5012532)