Bayesian Advantage of Re-Identification Attack in the Shuffle Model

2025/11/05 by Pengcheng Su, Su, Pengcheng, Haibo Cheng +3 · 1 citation
Computer Science · Engineering · #Bayesian network #Bayesian probability #Bayesian statistics #Cryptography and Data Security #Cryptography and Security (cs.CR) #Differential privacy #FOS: Computer and information sciences #Multiplicative function #Prior probability #Privacy-Preserving Technologies in Data #Probability distribution #Sample (material) #Smart Grid Security and Resilience #Upper and lower bounds

paper · pdf · doi:10.48550/arxiv.2511.03213

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2025/11/05 · openalex created_date 2025/11/07 · openalex updated_date 2026/07/28

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.

Citations

• Decomposition-Based Optimal Bounds for Privacy Amplification via Shuffling
• The Impact of Exposed Passwords on Honeyword Efficacy
• Analyzing the Shuffle Model through the Lens of Quantitative Information Flow
• Stronger Privacy Amplification by Shuffling for Rényi and Approximate Differential Privacy
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling
• On the Round Complexity of the Shuffle Model
• Local Differential Privacy and Its Applications: A Comprehensive Survey
• The Privacy Blanket of the Shuffle Model
• Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity
• Collecting Telemetry Data Privately
• Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias

Cited by

• Mutual Information Bounds in the Shuffle Model

Related

• Augmented Shuffle Protocols for Accurate and Robust Frequency Estimation under Differential Privacy
• Analyzing the Shuffle Model through the Lens of Quantitative Information Flow
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling
• Mutual Information Bounds in the Shuffle Model
• Differentially Private Histograms in the Shuffle Model from Fake Users