Abstract
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 β_n(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_n⁺(P, Q) = β_n(P,Q) - 1/n and Adv_n^×(P, Q) = n · β_n(P,Q), respectively. We derive exact analytical expressions and asymptotic characterizations of β_n(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.