On the Round Complexity of the Shuffle Model

• URL: http://arxiv.org/abs/2009.13510v1
• Date: Mon, 28 Sep 2020 17:57:42 GMT
• Title: On the Round Complexity of the Shuffle Model
• Authors: Amos Beimel, Iftach Haitner, Kobbi Nissim, Uri Stemmer
• Abstract summary: The shuffle model of differential privacy was proposed as a viable model for performing distributed differentially private computations. We show how two parties can use one round of the shuffle to send secret messages without having to first establish a secret key. We examine differentially private computations in the shuffle model that do not require the assumption of an honest majority.
• Score: 25.454520433661646
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The shuffle model of differential privacy was proposed as a viable model for performing distributed differentially private computations. Informally, the model consists of an untrusted analyzer that receives messages sent by participating parties via a shuffle functionality, the latter potentially disassociates messages from their senders. Prior work focused on one-round differentially private shuffle model protocols, demonstrating that functionalities such as addition and histograms can be performed in this model with accuracy levels similar to that of the curator model of differential privacy, where the computation is performed by a fully trusted party. Focusing on the round complexity of the shuffle model, we ask in this work what can be computed in the shuffle model of differential privacy with two rounds. Ishai et al. [FOCS 2006] showed how to use one round of the shuffle to establish secret keys between every two parties. Using this primitive to simulate a general secure multi-party protocol increases its round complexity by one. We show how two parties can use one round of the shuffle to send secret messages without having to first establish a secret key, hence retaining round complexity. Combining this primitive with the two-round semi-honest protocol of Applebaun et al. [TCC 2018], we obtain that every randomized functionality can be computed in the shuffle model with an honest majority, in merely two rounds. This includes any differentially private computation. We then move to examine differentially private computations in the shuffle model that (i) do not require the assumption of an honest majority, or (ii) do not admit one-round protocols, even with an honest majority. For that, we introduce two computational tasks: the common-element problem and the nested-common-element problem, for which we show separations between one-round and two-round protocols.

Related papers

• Differential Privacy on Trust Graphs [54.55190841518906]
  We study differential privacy (DP) in a multi-party setting where each party only trusts a (known) subset of the other parties with its data. We give a DP algorithm for aggregation with a much better privacy-utility trade-off than in the well-studied local model of DP.
  arXiv  Detail & Related papers  (2024-10-15T20:31:04Z)
• 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)
• Beyond Statistical Estimation: Differentially Private Individual Computation via Shuffling [21.031062710893867]
  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.
  arXiv  Detail & Related papers  (2024-06-26T07:53:48Z)
• Towards a Generalist and Blind RGB-X Tracker [91.36268768952755]
  We develop a single model tracker that can remain blind to any modality X during inference time. Our training process is extremely simple, integrating multi-label classification loss with a routing function. Our generalist and blind tracker can achieve competitive performance compared to well-established modal-specific models.
  arXiv  Detail & Related papers  (2024-05-28T03:00:58Z)
• Differentially Private Aggregation via Imperfect Shuffling [64.19885806149958]
  We introduce the imperfect shuffle differential privacy model, where messages are shuffled in an almost uniform manner before being observed by a curator for private aggregation. We show that surprisingly, there is no additional error overhead necessary in the imperfect shuffle model.
  arXiv  Detail & Related papers  (2023-08-28T17:34:52Z)
• Just One Byte (per gradient): A Note on Low-Bandwidth Decentralized Language Model Finetuning Using Shared Randomness [86.61582747039053]
  Language model training in distributed settings is limited by the communication cost of exchanges. We extend recent work using shared randomness to perform distributed fine-tuning with low bandwidth.
  arXiv  Detail & Related papers  (2023-06-16T17:59:51Z)
• Concurrent Shuffle Differential Privacy Under Continual Observation [60.127179363119936]
  We study the private continual summation problem (a.k.a. the counter problem) We show that the concurrent shuffle model allows for significantly improved error compared to a standard (single) shuffle model.
  arXiv  Detail & Related papers  (2023-01-29T20:42:54Z)
• Learning from aggregated data with a maximum entropy model [73.63512438583375]
  We show how a new model, similar to a logistic regression, may be learned from aggregated data only by approximating the unobserved feature distribution with a maximum entropy hypothesis. We present empirical evidence on several public datasets that the model learned this way can achieve performances comparable to those of a logistic model trained with the full unaggregated data.
  arXiv  Detail & Related papers  (2022-10-05T09:17:27Z)
• Tight Differential Privacy Guarantees for the Shuffle Model with $k$-Randomized Response [6.260747047974035]
  Most differentially private (DP) algorithms assume a third party inserts noise to queries made on datasets, or a local model where the users locally perturb their data. The recently proposed shuffle model is an intermediate framework between the central and the local paradigms. We perform experiments on both synthetic and real data to compare the privacy-utility trade-off of the shuffle model with that of the central one privatized.
  arXiv  Detail & Related papers  (2022-05-18T10:44:28Z)
• Shuffle Private Stochastic Convex Optimization [20.379311972125034]
  In shuffle privacy, each user sends a collection of randomized messages to a trusted shuffler. The shuffler randomly permutes these messages, and the resulting shuffled collection of messages must satisfy differential privacy. We present interactive shuffle protocols for convex optimization.
  arXiv  Detail & Related papers  (2021-06-17T20:44:00Z)

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.