Concurrent Shuffle Differential Privacy Under Continual Observation
Authors: Jay Tenenbaum, Haim Kaplan, Yishay Mansour, Uri Stemmer
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce the concurrent shuffle model of differential privacy. In this model we have multiple concurrent shufflers permuting messages from different, possibly overlapping, batches of users. Similarly to the standard (single) shuffle model, the privacy requirement is that the concatenation of all shuffled messages should be differentially private. We study the private continual summation problem (a.k.a. the counter problem) and show that the concurrent shuffle model allows for significantly improved error compared to a standard (single) shuffle model. Specifically, we give a summation algorithm with error O(n1/(2k+1)) with k concurrent shufflers on a sequence of length n. Furthermore, we prove that this bound is tight for any k, even if the algorithm can choose the sizes of the batches adaptively. For k = log n shufflers, the resulting error is polylogarithmic, much better than Θ(n1/3) which we show is the smallest possible with a single shuffler. |
| Researcher Affiliation | Collaboration | 1Google Research 2Blavatnik School of Computer Science, Tel Aviv University. |
| Pseudocode | Yes | Algorithm 1 Concurrent Shuffle Differential Privacy Under Continual Observation with k Shufflers |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. |
| Open Datasets | No | The paper defines the input as 'binary values' or 'bounded values in [0, 1]' but does not refer to specific, publicly available datasets for training, nor does it provide access information for such data. |
| Dataset Splits | No | The paper does not provide specific dataset split information for reproduction, as it focuses on theoretical analysis rather than empirical validation with real datasets. |
| Hardware Specification | No | The paper focuses on theoretical analysis and algorithm design and does not provide specific hardware details used for running experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers. |
| Experiment Setup | No | The paper provides algorithms but does not include specific experimental setup details such as concrete hyperparameter values or training configurations. |