Answers are grounded in this paper and cite their sources.
This work uncovers the impact of shuffle model on re-identification attacks, suggesting implications for cryptography and privacy protocols.
The shuffle model, which anonymizes data by randomly permuting user messages, has been widely adopted in both cryptography and differential privacy. In this work, we present the first systematic study of the Bayesian advantage in re-identifying a user's message under the shuffle model. We begin with a basic setting: one sample is drawn from a distribution P, and $n - 1$ samples are drawn from a distribution Q, after which all n samples are randomly shuffled. We define βₙ(P, Q) as the success probability of a Bayes-optimal adversary in identifying the sample from P, and define the additive and multiplicative Bayesian advantages as Advₙ⁺(P, Q) = βₙ(P,Q) - 1/n and Advₙ×(P, Q) = n · βₙ(P,Q), respectively. We derive exact analytical expressions and asymptotic characterizations of βₙ(P, Q), along with evaluations in several representative scenarios. Furthermore, we establish (nearly) tight mutual bounds between the additive Bayesian advantage and the total variation distance. Finally, we extend our analysis beyond the basic setting and present, for the first time, an upper bound on the success probability of Bayesian attacks in shuffle differential privacy. Specifically, when the outputs of n users -- each processed through an ε-differentially private local randomizer -- are shuffled, the probability that an attacker successfully re-identifies any target user's message is at most eε/n.
No takes yet. Share an insight, caveat, or question.
Su et al. (2025) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: