Beyond Statistical Estimation: Differentially Private Individual Computation via Shuffling

• URL: http://arxiv.org/abs/2406.18145v3
• Date: Thu, 30 Jan 2025 02:54:49 GMT
• Title: Beyond Statistical Estimation: Differentially Private Individual Computation via Shuffling
• Authors: Shaowei Wang, Changyu Dong, Xiangfu Song, Jin Li, Zhili Zhou, Di Wang, Han Wu,
• Abstract summary: This paper introduces a novel paradigm termed Private Individual Computation (PIC) PIC enables personalized outputs while preserving privacy, and enjoys privacy amplification through shuffling. We present an optimal randomizer, the Minkowski Response, designed for the PIC model to enhance utility.
• Score: 21.031062710893867
• License:
• Abstract: In data-driven applications, preserving user privacy while enabling valuable computations remains a critical challenge. Technologies like differential privacy have been pivotal in addressing these concerns. The shuffle model of DP requires no trusted curators and can achieve high utility by leveraging the privacy amplification effect yielded from shuffling. These benefits have led to significant interest in the shuffle model. However, the computation tasks in the shuffle model are limited to statistical estimation, making it inapplicable to real-world scenarios in which each user requires a personalized output. This paper introduces a novel paradigm termed Private Individual Computation (PIC), expanding the shuffle model to support a broader range of permutation-equivariant computations. PIC enables personalized outputs while preserving privacy, and enjoys privacy amplification through shuffling. We propose a concrete protocol that realizes PIC. By using one-time public keys, our protocol enables users to receive their outputs without compromising anonymity, which is essential for privacy amplification. Additionally, we present an optimal randomizer, the Minkowski Response, designed for the PIC model to enhance utility. We formally prove the security and privacy properties of the PIC protocol. Theoretical analysis and empirical evaluations demonstrate PIC's capability in handling non-statistical computation tasks, and the efficacy of PIC and the Minkowski randomizer in achieving superior utility compared to existing solutions.

Related papers

• Differentially Private Random Feature Model [52.468511541184895]
  We produce a differentially private random feature model for privacy-preserving kernel machines. We show that our method preserves privacy and derive a generalization error bound for the method.
  arXiv  Detail & Related papers  (2024-12-06T05:31:08Z)
• Pseudo-Probability Unlearning: Towards Efficient and Privacy-Preserving Machine Unlearning [59.29849532966454]
  We propose PseudoProbability Unlearning (PPU), a novel method that enables models to forget data to adhere to privacy-preserving manner. Our method achieves over 20% improvements in forgetting error compared to the state-of-the-art.
  arXiv  Detail & Related papers  (2024-11-04T21:27:06Z)
• Efficient Fault-Tolerant Quantum Protocol for Differential Privacy in the Shuffle Model [2.0794380287086214]
  We present a quantum protocol which implicitly implements a random shuffle to realize differential privacy in the shuffle model. The shuffle model amplifies outcomes achievable from data contributors. Examples include implementing the shuffle via mix-networks, or shuffling via a trusted third-party. We propose a quantum version of the protocol using entanglement of quantum states and show that the shuffle can be implemented without these extra requirements.
  arXiv  Detail & Related papers  (2024-09-06T04:53:19Z)
• Segmented Private Data Aggregation in the Multi-message Shuffle Model [9.298982907061099]
  We pioneer the study of segmented private data aggregation within the multi-message shuffle model of differential privacy. Our framework introduces flexible privacy protection for users and enhanced utility for the aggregation server. Our framework achieves a reduction of about 50% in estimation error compared to existing approaches.
  arXiv  Detail & Related papers  (2024-07-29T01:46:44Z)
• Enhanced Privacy Bound for Shuffle Model with Personalized Privacy [32.08637708405314]
  Differential Privacy (DP) is an enhanced privacy protocol which introduces an intermediate trusted server between local users and a central data curator. It significantly amplifies the central DP guarantee by anonymizing and shuffling the local randomized data. This work focuses on deriving the central privacy bound for a more practical setting where personalized local privacy is required by each user.
  arXiv  Detail & Related papers  (2024-07-25T16:11:56Z)
• 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)
• 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)
• TernaryVote: Differentially Private, Communication Efficient, and Byzantine Resilient Distributed Optimization on Heterogeneous Data [50.797729676285876]
  We propose TernaryVote, which combines a ternary compressor and the majority vote mechanism to realize differential privacy, gradient compression, and Byzantine resilience simultaneously. We theoretically quantify the privacy guarantee through the lens of the emerging f-differential privacy (DP) and the Byzantine resilience of the proposed algorithm.
  arXiv  Detail & Related papers  (2024-02-16T16:41:14Z)
• A Randomized Approach for Tight Privacy Accounting [63.67296945525791]
  We propose a new differential privacy paradigm called estimate-verify-release (EVR) EVR paradigm first estimates the privacy parameter of a mechanism, then verifies whether it meets this guarantee, and finally releases the query output. Our empirical evaluation shows the newly proposed EVR paradigm improves the utility-privacy tradeoff for privacy-preserving machine learning.
  arXiv  Detail & Related papers  (2023-04-17T00:38:01Z)
• Privacy Amplification via Shuffled Check-Ins [2.3333090554192615]
  We study a protocol for distributed computation called shuffled check-in. It achieves strong privacy guarantees without requiring any further trust assumptions beyond a trusted shuffler. We show that shuffled check-in achieves tight privacy guarantees through privacy amplification.
  arXiv  Detail & Related papers  (2022-06-07T09:55:15Z)
• Just Fine-tune Twice: Selective Differential Privacy for Large Language Models [69.66654761324702]
  We propose a simple yet effective just-fine-tune-twice privacy mechanism to achieve SDP for large Transformer-based language models. Experiments show that our models achieve strong performance while staying robust to the canary insertion attack.
  arXiv  Detail & Related papers  (2022-04-15T22:36:55Z)

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.