Sketches-based join size estimation under local differential privacy

• URL: http://arxiv.org/abs/2405.11419v1
• Date: Sun, 19 May 2024 01:21:54 GMT
• Title: Sketches-based join size estimation under local differential privacy
• Authors: Meifan Zhang, Xin Liu, Lihua Yin,
• Abstract summary: Join size estimation on sensitive data poses a risk of privacy leakage. Local differential privacy (LDP) is a solution to preserve privacy while collecting sensitive data. We introduce a novel algorithm called LDPJoinSketch for sketch-based join size estimation under LDP.
• Score: 3.0945730947183203
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Join size estimation on sensitive data poses a risk of privacy leakage. Local differential privacy (LDP) is a solution to preserve privacy while collecting sensitive data, but it introduces significant noise when dealing with sensitive join attributes that have large domains. Employing probabilistic structures such as sketches is a way to handle large domains, but it leads to hash-collision errors. To achieve accurate estimations, it is necessary to reduce both the noise error and hash-collision error. To tackle the noise error caused by protecting sensitive join values with large domains, we introduce a novel algorithm called LDPJoinSketch for sketch-based join size estimation under LDP. Additionally, to address the inherent hash-collision errors in sketches under LDP, we propose an enhanced method called LDPJoinSketch+. It utilizes a frequency-aware perturbation mechanism that effectively separates high-frequency and low-frequency items without compromising privacy. The proposed methods satisfy LDP, and the estimation error is bounded. Experimental results show that our method outperforms existing methods, effectively enhancing the accuracy of join size estimation under LDP.

Related papers

• Lightweight Federated Learning with Differential Privacy and Straggler Resilience [19.94124499453864]
  Federated learning (FL) enables collaborative model training through model parameter exchanges instead of raw data. To avoid potential inference attacks from exchanged parameters, differential privacy (DP) offers rigorous guarantee against various attacks. We propose LightDP-FL, a novel lightweight scheme that ensures provable DP against untrusted peers and server.
  arXiv  Detail & Related papers  (2024-12-09T00:54:00Z)
• Differentially Private Clustered Federated Learning [4.768272342753616]
  Federated learning (FL) often incorporates differential privacy (DP) to provide rigorous data privacy guarantees. Previous works attempted to address high structured data heterogeneity in vanilla FL settings through clustering clients (a.k.a clustered FL) We propose an algorithm for differentially private clustered FL, which is robust to the DP noise in the system and identifies the underlying clients' clusters correctly.
  arXiv  Detail & Related papers  (2024-05-29T17:03:31Z)
• Noise Variance Optimization in Differential Privacy: A Game-Theoretic Approach Through Per-Instance Differential Privacy [7.264378254137811]
  Differential privacy (DP) can measure privacy loss by observing the changes in the distribution caused by the inclusion of individuals in the target dataset. DP has been prominent in safeguarding datasets in machine learning in industry giants like Apple and Google. We propose per-instance DP (pDP) as a constraint, measuring privacy loss for each data instance and optimizing noise tailored to individual instances.
  arXiv  Detail & Related papers  (2024-04-24T06:51:16Z)
• Closed-Form Bounds for DP-SGD against Record-level Inference [18.85865832127335]
  We focus on the popular DP-SGD algorithm, and derive simple closed-form bounds. We obtain bounds for membership inference that match state-of-the-art techniques. We present a novel data-dependent bound against attribute inference.
  arXiv  Detail & Related papers  (2024-02-22T09:26:16Z)
• Partial Identification with Noisy Covariates: A Robust Optimization Approach [94.10051154390237]
  Causal inference from observational datasets often relies on measuring and adjusting for covariates. We show that this robust optimization approach can extend a wide range of causal adjustment methods to perform partial identification. Across synthetic and real datasets, we find that this approach provides ATE bounds with a higher coverage probability than existing methods.
  arXiv  Detail & Related papers  (2022-02-22T04:24:26Z)
• Wireless Federated Learning with Limited Communication and Differential Privacy [21.328507360172203]
  This paper investigates the role of dimensionality reduction in efficient communication and differential privacy (DP) of the local datasets at the remote users for over-the-air computation (AirComp)-based federated learning (FL) model.
  arXiv  Detail & Related papers  (2021-06-01T15:23:12Z)
• Lossless Compression of Efficient Private Local Randomizers [55.657133416044104]
  Locally Differentially Private (LDP) Reports are commonly used for collection of statistics and machine learning in the federated setting. In many cases the best known LDP algorithms require sending prohibitively large messages from the client device to the server. This has led to significant efforts on reducing the communication cost of LDP algorithms.
  arXiv  Detail & Related papers  (2021-02-24T07:04:30Z)
• Learning with User-Level Privacy [61.62978104304273]
  We analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution. We derive an algorithm that privately answers a sequence of $K$ adaptively chosen queries with privacy cost proportional to $tau$, and apply it to solve the learning tasks we consider.
  arXiv  Detail & Related papers  (2021-02-23T18:25:13Z)
• A One-Pass Private Sketch for Most Machine Learning Tasks [48.17461258268463]
  Differential privacy (DP) is a compelling privacy definition that explains the privacy-utility tradeoff via formal, provable guarantees. We propose a private sketch that supports a multitude of machine learning tasks including regression, classification, density estimation, and more. Our sketch consists of randomized contingency tables that are indexed with locality-sensitive hashing and constructed with an efficient one-pass algorithm.
  arXiv  Detail & Related papers  (2020-06-16T17:47:48Z)
• Differentially Private Federated Learning with Laplacian Smoothing [72.85272874099644]
  Federated learning aims to protect data privacy by collaboratively learning a model without sharing private data among users. An adversary may still be able to infer the private training data by attacking the released model. Differential privacy provides a statistical protection against such attacks at the price of significantly degrading the accuracy or utility of the trained models.
  arXiv  Detail & Related papers  (2020-05-01T04:28:38Z)
• User-Level Privacy-Preserving Federated Learning: Analysis and Performance Optimization [77.43075255745389]
  Federated learning (FL) is capable of preserving private data from mobile terminals (MTs) while training the data into useful models. From a viewpoint of information theory, it is still possible for a curious server to infer private information from the shared models uploaded by MTs. We propose a user-level differential privacy (UDP) algorithm by adding artificial noise to the shared models before uploading them to servers.
  arXiv  Detail & Related papers  (2020-02-29T10:13:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.