Augmented Shuffle Protocols for Accurate and Robust Frequency Estimation under Differential Privacy

• URL: http://arxiv.org/abs/2504.07362v1
• Date: Thu, 10 Apr 2025 01:06:05 GMT
• Title: Augmented Shuffle Protocols for Accurate and Robust Frequency Estimation under Differential Privacy
• Authors: Takao Murakami, Yuichi Sei, Reo Eriguchi,
• Abstract summary: We propose three concrete protocols providing DP and robustness against the two attacks.<n>Our first protocol generates the number of dummy values for each item from a binomial distribution.<n>Our second protocol significantly improves the utility of our first protocol by introducing a novel dummy-count distribution.
• Score: 4.527947047128005
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The shuffle model of DP (Differential Privacy) provides high utility by introducing a shuffler that randomly shuffles noisy data sent from users. However, recent studies show that existing shuffle protocols suffer from the following two major drawbacks. First, they are vulnerable to local data poisoning attacks, which manipulate the statistics about input data by sending crafted data, especially when the privacy budget epsilon is small. Second, the actual value of epsilon is increased by collusion attacks by the data collector and users. In this paper, we address these two issues by thoroughly exploring the potential of the augmented shuffle model, which allows the shuffler to perform additional operations, such as random sampling and dummy data addition. Specifically, we propose a generalized framework for local-noise-free protocols in which users send (encrypted) input data to the shuffler without adding noise. We show that this generalized protocol provides DP and is robust to the above two attacks if a simpler mechanism that performs the same process on binary input data provides DP. Based on this framework, we propose three concrete protocols providing DP and robustness against the two attacks. Our first protocol generates the number of dummy values for each item from a binomial distribution and provides higher utility than several state-of-the-art existing shuffle protocols. Our second protocol significantly improves the utility of our first protocol by introducing a novel dummy-count distribution: asymmetric two-sided geometric distribution. Our third protocol is a special case of our second protocol and provides pure epsilon-DP. We show the effectiveness of our protocols through theoretical analysis and comprehensive experiments.

Related papers

• Experimental Simulation of Two Pulses and Three Pulses Coherent One Way Quantum Key Distribution Protocol in Noisy/Noiseless and Wired/Wireless Environment [1.8638865257327277]
  Coherent One Way (COW) protocol is one of the most famous protocol because of its ease of hardware deployment. We demonstrate the encoding as well as decoding portions of the protocols under both noisy and noiseless scenario.
  arXiv  Detail & Related papers  (2024-09-23T11:02:52Z)
• Benchmarking Secure Sampling Protocols for Differential Privacy [3.0325535716232404]
  Two well-known models of Differential Privacy (DP) are the central model and the local model. Recently, many studies have proposed to achieve DP with Secure Multi-party Computation (MPC) in distributed settings.
  arXiv  Detail & Related papers  (2024-09-16T19:04:47Z)
• PriRoAgg: Achieving Robust Model Aggregation with Minimum Privacy Leakage for Federated Learning [49.916365792036636]
  Federated learning (FL) has recently gained significant momentum due to its potential to leverage large-scale distributed user data. The transmitted model updates can potentially leak sensitive user information, and the lack of central control of the local training process leaves the global model susceptible to malicious manipulations on model updates. We develop a general framework PriRoAgg, utilizing Lagrange coded computing and distributed zero-knowledge proof, to execute a wide range of robust aggregation algorithms while satisfying aggregated privacy.
  arXiv  Detail & Related papers  (2024-07-12T03:18:08Z)
• Beyond Statistical Estimation: Differentially Private Individual Computation via Shuffling [21.031062710893867]
  This paper introduces a novel paradigm termed Private Individual Computation (PIC)<n>PIC enables personalized outputs while preserving privacy, and enjoys privacy amplification through shuffling.<n>We present an optimal randomizer, the Minkowski Response, designed for the PIC model to enhance utility.
  arXiv  Detail & Related papers  (2024-06-26T07:53:48Z)
• 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)
• Bicoptor 2.0: Addressing Challenges in Probabilistic Truncation for Enhanced Privacy-Preserving Machine Learning [6.733212399517445]
  This paper focuses on analyzing the problems and proposing solutions for the probabilistic truncation protocol in existing PPML works. In terms of accuracy, we reveal that precision selections recommended in some of the existing works are incorrect. We propose a solution and a precision selection guideline for future works.
  arXiv  Detail & Related papers  (2023-09-10T01:43:40Z)
• Data post-processing for the one-way heterodyne protocol under composable finite-size security [62.997667081978825]
  We study the performance of a practical continuous-variable (CV) quantum key distribution protocol. We focus on the Gaussian-modulated coherent-state protocol with heterodyne detection in a high signal-to-noise ratio regime. This allows us to study the performance for practical implementations of the protocol and optimize the parameters connected to the steps above.
  arXiv  Detail & Related papers  (2022-05-20T12:37:09Z)
• Composably secure data processing for Gaussian-modulated continuous variable quantum key distribution [58.720142291102135]
  Continuous-variable quantum key distribution (QKD) employs the quadratures of a bosonic mode to establish a secret key between two remote parties. We consider a protocol with homodyne detection in the general setting of composable finite-size security. In particular, we analyze the high signal-to-noise regime which requires the use of high-rate (non-binary) low-density parity check codes.
  arXiv  Detail & Related papers  (2021-03-30T18:02:55Z)
• Round-robin differential phase-time-shifting protocol for quantum key distribution: theory and experiment [58.03659958248968]
  Quantum key distribution (QKD) allows the establishment of common cryptographic keys among distant parties. Recently, a QKD protocol that circumvents the need for monitoring signal disturbance, has been proposed and demonstrated in initial experiments. We derive the security proofs of the round-robin differential phase-time-shifting protocol in the collective attack scenario. Our results show that the RRDPTS protocol can achieve higher secret key rate in comparison with the RRDPS, in the condition of high quantum bit error rate.
  arXiv  Detail & Related papers  (2021-03-15T15:20:09Z)
• On the Practicality of Differential Privacy in Federated Learning by Tuning Iteration Times [51.61278695776151]
  Federated Learning (FL) is well known for its privacy protection when training machine learning models among distributed clients collaboratively. Recent studies have pointed out that the naive FL is susceptible to gradient leakage attacks. Differential Privacy (DP) emerges as a promising countermeasure to defend against gradient leakage attacks.
  arXiv  Detail & Related papers  (2021-01-11T19:43:12Z)
• Entanglement purification by counting and locating errors with entangling measurements [62.997667081978825]
  We consider entanglement purification protocols for multiple copies of qubit states. We use high-dimensional auxiliary entangled systems to learn about number and positions of errors in the noisy ensemble.
  arXiv  Detail & Related papers  (2020-11-13T19:02:33Z)

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.