arXiv CSopen access

Cross-Silo De-Anonymization Under Local Differential Privacy: Threat Model, Phase Transition, and Coordination Necessity

Cross-Silo De-Anonymization Under Local Differential Privacy: Threat Model, Phase Transition, and Coordination Necessity Aiping Li∗

Ziniu Liu

arXiv:2606.16763v1 [cs.CR] 15 Jun 2026

National University of Defense Technology {liuzn nudt, liaiping}@nudt.edu.cn June 16, 2026

Abstract When a person’s records appear in k independent data silos, each protected by (ε, δ)differential privacy, standard composition yields a valid (kε, kδ)-DP guarantee for the joint output. This worst-case bound, however, does not answer the concrete inference question: at what k can an adversary actually identify a target person? This paper develops the informationtheoretic framework needed to answer that question. We introduce cross-silo person-level DP (XSP-DP), a Pufferfish-style privacy notion whose adjacency relation captures all records of a singleP personPacross all silos simultaneously, and verify that the standard basic composition bound ( i εi , i δi )-DP carries over to this adjacency model. Within this framework we prove that de-anonymization undergoes a phase transition at k ∗ = Θ(log n/ε2 ) (population size n, per-silo RR parameter ε): a Fano lower bound shows any estimator fails for k ≪ k ∗ , while a matching maximum-likelihood upper bound shows the attack succeeds for k ≫ k ∗ . An explicit XOR + randomized-response construction demonstrates information synergy: each silo’s output is individually uninformative about the target (I(Z; Yi ) = 0), yet the joint mutual information is strictly positive. For non-coordinated binary randomized-response mechanisms, we prove that de-anonymization is inevitable once k exceeds the threshold, establishing that cross-silo coordination is necessary. These results provide a baseline threat model and Θ-level threshold for cross-silo inference attacks under local DP. Sharp constants, second-order thresholds, and spectral characterizations of the phase transition are developed in a companion paper; coordinated defense protocols and their system-level guarantees are treated separately.

1

Introduction

1.1

Motivation

Consider a network of k hospitals participating in a federated learning pipeline. Each hospital trains on its own patient cohort and publishes a differentially private summary—a gradient, a prompt refinement, or an aggregated statistic. Each publication individually satisfies (ε, δ)-DP. Standard composition guarantees that the joint publication satisfies (kε, kδ)-DP, which at small k appears acceptable. But the composition bound alone does not answer a concrete adversarial question: at what value of k can a curious adversary, who sends one innocuous-looking query to each hospital’s API and assembles the k responses, actually identify a target person among n patients? ∗

Corresponding author.

1

This paper shows that de-anonymization undergoes a sharp phase transition: below a critical threshold k ∗ = Θ(log n/ε2 ), any estimator fails with non-negligible probability; above it, a maximum-likelihood adversary succeeds with high probability. For binary randomized-response mechanisms, no non-coordinated defense can prevent this.

1.2

Beyond Composition: The Inference Question

When a person’s data appear in k silos and each silo independently applies an (ε, δ)-DP mechanism, standard basic composition [8] gives a valid (kε, kδ)-DP guarantee for the joint output. This bound is well-known and straightforward to apply. The question we ask is different and complementary: at what value of k does the accumulated leakage actually allow an adversary to identify a target person? The (kε, kδ)-DP guarantee degrades linearly in k, but it is a worst-case bound that does not pinpoint the threshold at which de-anonymization transitions from impossible to feasible. Answering this question requires an information-theoretic analysis—relating per-silo mutual information to the adversary’s identification probability—rather than purely compositional reasoning. Pufferfish privacy [17] can in principle model cross-silo threats, but it requires specifying a distribution family over secrets and world states that is difficult to instantiate concretely for federated systems. Existing multi-agent DP work (e.g., [7, 4]) focuses on centralized composition or heterogeneous local sensitivity, not on the inference risk studied here. We provide: • a concrete adjacency relation—person-level cross-silo adjacency (Theorem 3.1)—that captures the threat model exactly; • tight information-theoretic bounds on how many silos suffice for de-anonymization; • a formal impossibility result (for randomized response) that rules out local-only defenses.

1.3

Contributions

We make four contributions. 1. XSP-DP (Theorem 3.2). We define cross-silo person-level DP via a new adjacency relation D ∼ps D′ that treats all records of a single person across silos as the protected unit. 2. Composition under XSP-DP (Theorem 4.1). If each silo i satisfies (εi , δi )-DP P at personP level granularity and mechanisms are independent, the joint mechanism satisfies ( i εi , i δi )XSP-DP, recovering the standard basic composition guarantee within our cross-silo adjacency model. 3. Phase transition theorem (Theorems 6.4, 6.5 and 6.7). Under Assumptions A1–A4, the de-anonymization error probability satisfies: k < (1 − δ)k ∗ ⇒ Pe ≥ δ − o(1), k > (1 + δ)k ∗ ⇒ Pe ≤ n−δ → 0, for any δ ∈ (0, 1), establishing a sharp phase transition at k ∗ = Θ(log n/I1 ) where I1 = I(Z; Yi ) is the single-silo mutual information.

2

4. Impossibility for randomized response (Theorem 7.3). Any non-coordinated collection of binary ε-DP randomized-response mechanisms with per-silo information I1 ≥ α > 0 fails to prevent de-anonymization for k > 2(1 + δ) ln n/α. The Fano converse (Theorem 6.4), which holds for any mechanism, shows that the threshold scale k = Θ(ln n/I1 ) is universal.

1.4

Paper Organization

Section 2 reviews related work. Section 3 introduces the formal model, adjacency relation, and assumptions. Section 4 verifies that standard composition applies under XSP-DP. Section 5 presents the XOR construction and PID analysis. Section 6 proves the phase transition theorems. Section 7 proves the impossibility result. Section 8 discusses implications for coordinated defense. Section 9 presents synthetic experiments validating the threshold formula. Section 10 concludes.

2

Related Work

Differential privacy composition. The foundational composition theorems of Dwork et al. [8] establish that the sequential composition of an ε1 -DP and an ε2 -DP p mechanism yields (ε1 + ε2 )-DP, and extensions to advanced composition reduce the total cost to O(ε k log(1/δ)) for k mechanisms [10]. Renyi DP [21] and zero-concentrated DP [2] provide tighter accounting under composition. These results readily apply to the cross-silo setting via standard sequential composition: if a person’s data appear in k silos, the joint output is (kε, kδ)-DP. However, this worst-case bound does not answer the inference question of how many silos suffice for an adversary to actually identify a target person—a gap that motivates our work. Cross-silo and federated learning privacy. Federated learning [19] has spurred a large literature on privacy under model aggregation. DP-SGD [1] clips and noises local gradients; follow-on work analyzes amplification by sampling [21] and shuffling [11]. In the cross-silo federated setting, each participating organization holds a distinct local dataset and runs its own mechanism before communicating with a central server. Prior work assumes that each silo’s output is locally DP with respect to that silo’s records [16], without analyzing the concrete de-anonymization risk that arises when an adversary queries multiple silos about the same person. Our model formalizes this threat and provides tight information-theoretic bounds on when identification becomes feasible. Membership and attribute inference attacks. Shokri et al. [23] demonstrate empirically that ML model outputs can reveal whether a given record was in the training set. Subsequent attacks have grown increasingly effective [3, 26]. In multi-party settings, passive inference across parties has been studied in the context of collaborative inference [13] and model inversion [12], but these works do not provide formal lower bounds on the number of queries needed for de-anonymization or characterize the information-theoretic phase transition we prove here. De-anonymization and linkage attacks. Narayanan and Shmatikoff [22] demonstrate that auxiliary information from one database can de-anonymize records in another, even after sanitization. Sweeney’s k-anonymity [24] and its successors (ℓ-diversity, t-closeness) attempt to limit such linkage, but have no formal DP guarantees. On the theoretical side, Dinur and Nissim [5] show that Ω(n) approximately-correct answers to linear queries over a database of n individuals suffice to reconstruct the database; our result is complementary—we characterize how many independent agents an adversary must query to re-identify a single target under local DP.

3

Information-theoretic privacy bounds. Fano’s inequality has been used to lower-bound minimax estimation error in statistical estimation [27] and in private learning [6]. Duchi, Jordan, and Wainwright [6] establish minimax rates for locally private estimation using Fano-style arguments, but focus on utility (estimation error) rather than identity leakage across silos. Our use of Fano to lower-bound de-anonymization error, combined with a matching upper bound via the ML attack, is technically distinct: we study identification (not estimation) in a federated multi-silo model. Pufferfish and correlated privacy. Pufferfish privacy [17] extends DP to arbitrary secret classes and world-state distributions, subsuming models with correlated data. Blowfish [15] instantiates Pufferfish with graph-structured correlations. Our XSP-DP (Theorem 3.2) can be viewed as a tractable instantiation of Pufferfish where the secret class is the cross-silo person identity and mechanisms are local. The key distinction is that we derive explicit, computable lower bounds and phase-transition thresholds, whereas the general Pufferfish framework does not provide such tight constructive results. Information synergy and PID. The Partial Information Decomposition (PID) framework of Williams and Beer [25] decomposes mutual information into unique, redundant, and synergistic components. Positive synergy (where the joint observation reveals more than the sum of individual contributions) has been studied in neuroscience [18] and cryptography [14]. Our XOR+RR construction (Theorem 5.1) provides a clean example of pure synergy in a DP-constrained multi-agent setting: each silo’s output is individually uninformative, yet two outputs together reveal the target completely in the limit. To our knowledge, this is the first result connecting PID synergy to cross-silo privacy leakage under DP. Multi-agent and distributed DP. Recent work on DP for multi-agent learning includes privacypreserving multi-party computation [7], local DP in the shuffle model [4], and federated analytics [20]. Attempts to combine DP with multi-agent optimization (e.g., DP-ES, DP-MAS [20]) focus on utility preservation under per-agent local DP, not on the compositional leakage that arises when an adversary queries multiple agents about the same individual. The impossibility result in Theorem 7.3 shows that, in the binary RR-channel model, no non-coordinated collection of per-agent DP mechanisms can prevent de-anonymization once sufficiently many agents have been queried—motivating coordinated defense mechanisms such as ToM filtering and CoDef consensus.

3

Model, Definitions, and Assumptions

3.1

Setting

Let [n] = {1, . . . , n} be a population of persons. There are k silos indexed i ∈ [k]. Silo i holds a local dataset Di ∈ D∗ . Write D = (D1 , . . . , Dk ) for the tuple of all datasets. A sensitive attribute Z ∈ Z is a function of the cross-silo tuple: Z = g(D). Each silo i runs a randomized mechanism Mi : D∗ → Yi and publishes Yi = Mi (Di ). The joint mechanism is M(D) = (M1 (D1 ), . . . , Mk (Dk )). An adversary observes Y = (Y1 , . . . , Yk ) and attempts to infer Z.

3.2

Person-Level Cross-Silo Adjacency

Definition 3.1 (Person-level cross-silo adjacency). Two dataset tuples D, D′ ∈ (D∗ )k are personlevel cross-silo adjacent, written D ∼ps D′ , if there exists a person p ∈ [n] such that for every silo 4

i ∈ [k]: Di △ Di′ ⊆ Di (p) ∪ Di′ (p), where Di (p) denotes the (multi-)set of records in Di associated with person p. All records not associated with p are identical across D and D′ . Intuitively, D ∼ps D′ captures the scenario where person p “opts in or out” simultaneously across all silos. Definition 3.2 (XSP-DP: Cross-Silo Person-level DP). The joint mechanism M is (ε, Qδ)-XSP-DP if for all person-level cross-silo adjacent pairs D ∼ps D′ and all measurable sets S ⊆ i Yi : Pr[M(D) ∈ S] ≤ eε Pr[M(D′ ) ∈ S] + δ. Remark 3.3 (Relation to Pufferfish privacy). XSP-DP is a concrete instantiation of Pufferfish  privacy [17]. Formally, set the secret-pair class S = (sp,in , sp,out ) : p ∈ [n] where sp,in and sp,out denote “person p is present in all silos” and “person p is absent from all silos,” respectively; set the discriminative-pair class Q = S; and let the data-generating distribution family Θ be the set of all product distributions satisfying Assumption 1. Then (ε, δ)-Pufferfish privacy with respect to (S, Q, Θ) is equivalent to (ε, δ)-XSP-DP. This specialization makes the lower-bound analysis tractable: the structure of S (cross-silo presence/absence of a single person) enables the Fano and ML bounds in Section 6.

3.3

Synergy Gap and Order Parameter

Definition 3.4 (Synergy gap). Given the joint distribution of (Z, Y1 , . . . , Yk ), define the synergy gap ∆syn = Syn − Red, where Syn and Red are the synergy and redundancy terms in the Partial Information Decomposition (PID) of I(Z; Y1:k ) (see Section E for formal definitions). ∆syn > 0 indicates that the agents collectively reveal more about Z than the sum of their individual contributions; ∆syn < 0 indicates redundancy dominates. Definition 3.5 (Order parameter). The leakage order parameter at k silos is Φk =

I(Z; Y1 , . . . , Yk ) ∈ [0, 1]. H(Z)

A phase transition in Pe (k) near k ∗ corresponds to Φk crossing from near-zero to near-one.

3.4

Assumptions

Assumption 1 (Single-record). |Di (p)| ≤ 1 for every person p and every silo i. Each person contributes at most one record per silo. Assumption 2 (Independent non-interactive mechanisms). The mechanisms M1 , . . . , Mk are chosen independently, and each Mi operates only on Di . There is no cross-silo communication during mechanism execution. Assumption 3 (Conditional independence). Given the sensitive attribute Z, the silo outputs are conditionally independent: Yi ⊥ Yj | Z for all i ̸= j. 5

Assumption 4 (Uniform prior). The target person’s identity (equivalently, their sensitive attribute Z) is drawn uniformly: Z ∼ Uniform([n]). Remark 3.6. Assumption 3 is satisfied whenever each silo’s mechanism depends on Z only through independent local noise and independent local data. It is not satisfied in correlated-data models; we treat that setting as future work.

4

Composition Under XSP-DP

Proposition 4.1 (XSP-DP upper bound). Under Assumptions 1 and 2, if each Mi satisfies (εi , δi )DP
granularity within silo i, then the joint mechanism M = (M1 , . . . , Mk ) satisfies Pk Pkat person-level δ ε , i=1 i -XSP-DP. i=1 i Proof sketch. See Section A for the full proof. For pure DP (δi = 0): the max-divergence D∞ tenP ′ sorizes over independent product mechanisms, giving D∞ (M(D)∥M(D )) ≤ i D∞ (Mi (Di )∥Mi (Di′ )) ≤ P i εi . For approximate DP: we use the standard “good-set” decomposition. S For each silo i, define ε i Bi = {yi : Pi (yi ) > e Qi (yi )}; then PiP (Bi ) ≤ δi . On the complement of i Bi , every factor satisfies εi multiplicative factor. A union bound over the bad events the pure-DP ratio bound, giving the e P yields i δi , recovering the standard basic composition guarantee. Remark 4.2 (Relation to standard composition). Theorem 4.1 instantiates the well-known basic composition theorem [8] within the XSP-DP adjacency model. The bound matches the standard result because the cross-silo adjacency ∼ps changes at most one record per silo, and the mechanisms are independent. Remark 4.3 (Group privacy and δ amplification). When |Di (p)| ≤ ci (person p contributes up to ci records in silo i), the εi -DP guarantee amplifies to ci εi -DP for all ci records, and δi amplifies by a factor (eci εi − 1)/(eεi − 1) ≤ ci e(ci −1)εi .

5

Information Synergy: The XOR Construction

We show that individual-silo privacy can perfectly conceal a sensitive attribute while the joint observation reveals it—demonstrating that the privacy guarantees of individual silos do not compose as favorably as they might appear from each silo’s perspective alone. Proposition 5.1 (Synergy is strictly positive). Let ε > 0. Consider Z, U ∼ Bern(1/2) i.i.d., and define X1 = U, X2 = Z ⊕ U. Let Yi = Xi ⊕ Ei where Ei ∼ Bern(q) i.i.d. and q = 1/(1 + eε ) (the flip probability of RRε ). Then: (a) I(Z; Y1 ) = I(Z; Y2 ) = 0. (b) I(Z; Y1 , Y2 ) = 1 − Hb (2pq) > 0, where p = 1 − q. (c) For small ε: ∆syn = I(Z; Y1 , Y2 ) − I(Z; Y1 ) − I(Z; Y2 ) ≈

6

ε4 . 32 ln 2

Proof. See Section B for the full computation. (a) Y1 = U ⊕E1 . Since U ∼ Bern(1/2) is independent of Z and independent of E1 , we have Y1 ∼ Bern(1/2) regardless of Z. Hence I(Z; Y1 ) = 0. For Y2 : given any fixed Z, X2 = Z ⊕U ∼ Bern(1/2) since U ∼ Bern(1/2). Therefore Y2 = X2 ⊕ E2 ∼ Bern(1/2) regardless of Z, so I(Z; Y2 ) = 0. (b) Y1 ⊕ Y2 = (U ⊕ E1 ) ⊕ (Z ⊕ U ⊕ E2 ) = Z ⊕ (E1 ⊕ E2 ). The noise bit E1 ⊕ E2 ∼ Bern(2pq) (binary symmetric channel with crossover 2pq). Hence I(Z; Y1 ⊕ Y2 ) = 1 − Hb (2pq) > 0 for all ε > 0 (since 2pq < 1/2 for ε > 0). Since Y1 ⊕ Y2 is a function of (Y1 , Y2 ), this bounds I(Z; Y1 , Y2 ) from below, which together with the direct calculation gives equality. (c) For q = 1/(1 + eε ) ≈ 1/2 − ε/4 at small ε: 2pq = 2(1/2 + ε/4)(1/2 − ε/4) = 1/2 − ε2 /8, so Hb (2pq) ≈ 1 − ε4 /(32 ln 2), and I(Z; Y1 , Y2 ) ≈ ε4 /(32 ln 2). Since I(Z; Y1 ) = I(Z; Y2 ) = 0, we get ∆syn ≈ ε4 /(32 ln 2). Remark 5.2 (PID interpretation). Using the Williams–Beer Partial Information Decomposition (Section E), we have I(Z; Y1 , Y2 ) = Syn + I(Z; Y1 ) + I(Z; Y2 ) − Red. Since I(Z; Y1 ) = I(Z; Y2 ) = 0 and Red ≥ 0, the entire joint information comes from pure synergy: Syn = I(Z; Y1 , Y2 ).

6

Phase Transition Theorems

6.1

Key Lemma: Mutual Information Upper Bound

Lemma 6.1 (MI upper bound under A3). Under Assumption 3, for any k ≥ 1: I(Z; Y1 , . . . , Yk ) = kI1 −

k X

I(Yi ; Y1 , . . . , Yi−1 ) ≤ kI1 ,

i=2

where I1 = I(Z; Yi ) (identical for all i by symmetry). Proof. By the chain rule for mutual information: I(Z; Y1:k ) =

k X

I(Z; Yi | Y1:i−1 ).

i=1

Under Assumption 3 (Yi ⊥ Yj | Z), we apply the identity: I(Z; Yi | Y1:i−1 ) = I(Z; Yi ) − I(Yi ; Y1:i−1 ) + I(Yi ; Y1:i−1 | Z). Since Yi ⊥ Y1:i−1 | Z (by Assumption 3), the last term vanishes. Therefore: I(Z; Y1:k ) =

k X 

k X  I1 − I(Yi ; Y1:i−1 ) = kI1 − I(Yi ; Y1:i−1 ).

i=1

i=2

Since mutual information is non-negative, the sum subtracted is ≥ 0, giving the upper bound I(Z; Y1:k ) ≤ kI1 . Lemma 6.2 (Cmin and I1 for binary channels).
For the randomized response mechanism RRε with q = 1/(1 + eε ), let Cmin = DKL RRε (0) ∥ RRε (1) = (1 − 2q)ε and I1 = I(Z; Y ) for Z ∼ Bern(1/2) (both in nats). Then: (i) Global lower bound: Cmin ≥ 4 I1

for all ε > 0, with Cmin /I1 → 4 as ε → 0.

7

(ii) Small-ε asymptotic: Cmin /I1 = 4 + ε2 /6 + O(ε4 ) as ε → 0. (iii) No finite global upper bound: There is no constant c2 < ∞ such that Cmin ≤ c2 I1 holds for all ε > 0. The weaker bound Cmin ≥ ln 2 · I1 (which follows from (i)) is used in Theorem 7.3. Proof. Explicit formulas. In nats: Cmin = (1 − 2q)ε = ε tanh(ε/2), and I1 = ln 2 − Hb (q) (see Section F for Taylor series). We write t = ε/2 throughout. Global lower bound (i). Define g(ε) = Cmin − 4 I1 = ε tanh(t) − 4(ln 2 − Hbnats (q)). At ε = 0: q = 1/2, tanh(0) = 0, Hbnats (1/2) = ln 2, so g(0) = 0. We show g ′ (ε) > 0 for all ε > 0. Using dq/dε = −pq and dHbnats (q)/dq = ln(p/q) = ε: d(Cmin ) t = tanh(t) + , dε cosh2 (t)

t dI1 = ε pq = . dε 2 cosh2 (t)

Therefore: g ′ (ε) = tanh(t) +

  4t t 1 t − = tanh(t) − = sinh(t) cosh(t) − t . 2 2 2 2 cosh (t) 2 cosh (t) cosh (t) cosh (t)

Since cosh2 (t) > 0, it suffices to show sinh(t) cosh(t) > t for t > 0. This is equivalent to sinh(2t) > 2t, which holds because sinh(x) = x + x3 /6 + x5 /120 + · · · > x for all x > 0 (every term in the power series is strictly positive). Hence g ′ (ε) > 0 for all ε > 0, and g(0) = 0 implies g(ε) > 0 for all ε > 0, i.e., Cmin > 4 I1 . Asymptotic (ii). Using the Taylor series Cmin = ε2 /2 − ε4 /24 + O(ε6 ) and I1 = ε2 /8 − ε4 /64 + O(ε6 ) (both in nats): Cmin /I1 = 4 + ε2 /6 + O(ε4 ). No global upper bound (iii). For ε → ∞: Cmin = ε tanh(ε/2) ∼ ε while I1 → ln 2, so Cmin /I1 → ∞. Remark 6.3 (Unit convention). A common source of confusion: I1 ≈ ε2 /(8 ln 2) in bits, while Cmin ≈ ε2 /2 in nats. Computing the ratio (ε2 /2) / (ε2 /(8 ln 2)) = 4 ln 2 ≈ 2.77 mixes units and yields an incorrect constant. All results in this paper use a single unit (nats) consistently.

6.2

Fano Lower Bound on Error Probability

Theorem 6.4 (Fano lower bound). Under Assumptions 1–4, for any estimator Ẑ of Z from (Y1 , . . . , Yk ) (all information quantities in nats): Pe ≥ 1 −

kI1 + 1 . ln n

Consequently, for k ≤ (1 − δ)k ∗ with k ∗ = ln n/I1 : Pe ≥ δ −

1 . ln n

Proof. Fano’s inequality in nats gives: H(Z | Y1:k ) ≤ H(Pe ) + Pe ln(n − 1) ≤ 1 + Pe ln n, where H(Pe ) = −Pe ln Pe − (1 − Pe ) ln(1 − Pe ) ≤ ln 2 < 1 for all Pe . Also H(Z | Y1:k ) = H(Z) − I(Z; Y1:k ) = ln n − I(Z; Y1:k ). By Theorem 6.1, I(Z; Y1:k ) ≤ kI1 , so H(Z | Y1:k ) ≥ ln n − kI1 . Combining: ln n − kI1 ≤ 1 + Pe ln n, which rearranges to Pe ≥ 1 − (kI1 + 1)/ ln n. For k ≤ (1 − δ)k ∗ = (1 − δ) ln n/I1 : (kI1 + 1)/ ln n ≤ (1 − δ) + 1/ ln n, so Pe ≥ δ − 1/ ln n. 8

6.3

ML Upper Bound on Error Probability

Theorem 6.5 (ML upper bound). Under Assumptions 1–4, where each person p has attributes Zp,1 , . . . , Zp,k drawn i.i.d. Bern(1/2) and silo i observes Yi = RRε (Zp0 ,i ), the maximum-likelihood estimator satisfies: k  1 + e−B , B = log cosh 2ε . Pe ≤ (n − 1) · 2 ∗ In particular, for any δ ∈ (0, 1) and k ≥ (1 + δ) kML where ∗ kML =

we have Pe Θ(k ∗ ).

≤ n−δ

ln n − ln

≈

1+e−B 2

2 ln n 16 ln n ∗ 2 ≈ = 2 k 1 + O(ε ) , B ε2

(all logarithms natural; I1 in nats). The ML attack succeeds once k crosses

Proof. The union bound gives Pe ≤ bound on pairwise ML error is:

P

p̸=p0 Pr[p̂ = p | p0 ]. For a fixed pair (p0 , p), the Bhattacharyya

Pr[Score(p) ≥ Score(p0 ) | Zp0 , Zp ] ≤

k Y

β 1[Zp0 ,i ̸=Zp,i ] ,

i=1

p where β = 2 q(1 − q) = e−B is the Bhattacharyya coefficient. Taking expectation over the random iid

attributes Zp,i ∼ Bern(1/2): k k    k Y Y   β 1+β 1 + = EZp Pr[·] ≤ E[β 1[Zp0 ,i ̸=Zp,i ] ] = . 2 2 2 i=1

i=1 −B

Summing over n−1 competitors gives the stated bound. Setting it ≤ n−δ : k ≥ (1+δ) ln n / (− ln 1+e2 ). −B For small ε: − ln 1+e2 ≈ B/2 ≈ ε2 /16, and I1nats ≈ ε2 /8, so CML ≈ 2. See Section D for the full derivation. Remark 6.6 (Constant-factor gap). The Fano bound (Theorem 6.4) and ML bound (Theorem 6.5) together establish that k ∗ = Θ(log n/I1 ) is the threshold, up to a constant factor. Analytically, CML ≈ 2 for small ε; empirically the crossing of Pe = 0.5 occurs at ≈ 1.5 k ∗ (Section 9). The factor-of-2 analytic gap is inherent in the union-bound argument, which is not tight when most competitors are easy to distinguish. Corollary 6.7 (Sharp threshold). Under Assumptions 1–4 and Theorem 6.2, define k∗ =

ln n I1

where I1 is in nats throughout. Then for any δ ∈ (0, 1) and n sufficiently large: k < (1 − δ)k ∗ =⇒ Pe ≥ δ − o(1), k > (1 + δ)k ∗ =⇒ Pe ≤ n−Ω(δ) . Under the binary randomized-response model: 

log n k (n, ε) = Θ ε2 ∗

where log denotes natural logarithm throughout. 9

 ,

Proof. The lower-bound direction (k < (1 − δ)k ∗ ⇒ Pe ≥ δ − o(1)) is Theorem 6.4. For the ∗ ∗ upper-bound direction, Theorem 6.5 gives Pe ≤ n−δ once k ≥ (1 + δ)kML where kML = ln n/CML . ∗ ∗ ∗ nats By Theorem F.1, CML ≥ I1 /2 for all ε > 0, so kML ≤ 2k (with k = ln n/I1 ). Hence k ≥ 2(1 + δ)k ∗ suffices for Pe ≤ n−δ . Since the constant factor 2 is absorbed into Θ(·) in the statement k ∗ = Θ(log n/ε2 ), and the second line of the corollary uses n−Ω(δ) (which hides the constant in the exponent), we have the stated result for any k > C(1 + δ)k ∗ with C = 2.

7

Impossibility of Non-Coordinated Defense

7.1

Tightness of the Upper Bound

P Theorem 7.1 (Tightness of Proposition 4.1). The bound i εi in Theorem T 4.1 is achieved. Specifically, for the Laplace mechanism with i.i.d. outputs and the event S = i {Yi > 1}: Pr[M(D) ∈ S] = e

P

i εi

· Pr[M(D′ ) ∈ S]

for appropriately chosen D ∼ps D′ . Proof. Consider queries fi (Di ) = xi ∈ R with sensitivity ∆f = 1. The Laplace mechanism outputs Yi = fi (Di ) + Lap(1/εi ). Take adjacent datasets Di , Di′ with fi (Di ) = 1, fi (Di′ ) = 0 (shift of 1, within sensitivity 1). Then: Pr[Yi > 1 | Di ] 1/2 Pr[Lap(1/εi ) > 0] = eεi . = = ′ Pr[Yi > 1 | Di ] Pr[Lap(1/εi ) > −1] (1/2)e−εi T ′ By i {Yi > 1} satisfies Pr[M(D) ∈ S]/ Pr[M(D ) ∈ S] = P independence, the product event S = ε i e i , meeting the XSP-DP bound of Theorem 4.1 with equality.

7.2

Impossibility Theorem

Definition 7.2 (Non-coordinated mechanisms). A collection of mechanisms {Mi } is non-coordinated if: NC1 (Local view): Each Mi accesses only Di . NC2 (Independent randomness): The random seeds of Mi and Mj are independent for i ̸= j. NC3 (Simultaneous design): The mechanism Mi is fixed before observing any Dj with j ̸= i. Theorem 7.3 (Utility–Privacy barrier). Let {Mi } be a non-coordinated collection of mechanisms satisfying Assumptions 1, 2 and 4, where each silo applies a binary symmetric channel—i.e., each person p contributes a binary attribute Zp,i ∼ Bern(1/2) and silo i publishes Yi = RRε (Zp0 ,i ) for some ε > 0, yielding per-silo mutual information I1 = I(Z; Yi ) ≥ α > 0 (all information quantities in nats). Then the ML adversary achieves Pe ≤ n−δ once k ≥

2(1 + δ) ln n . α

In particular, no non-coordinated ε-DP mechanism collection operating binary symmetric channels with I1 ≥ α can prevent de-anonymization for k in this regime.

10

Proof. We verify Assumption 3. The datasets D = (D1 , . . . , Dk ) are fixed; Z is the random target identity. The output Yi = Mi (Di ; Ri ) depends on Z through Di (Z)—the record of person Z in silo i—which gives I1 = I(Z; Yi ) ≥ α > 0 when Di (Z) varies non-trivially with Z. Conditioned on Z = z, the record Di (z) is a fixed quantity (part of the fixed dataset), so Yi is random only through Ri . By NC2, Ri ⊥ Rj for i ̸= j, hence Yi ⊥ Yj | Z, verifying Assumption 3. (This conditional independence does not imply Yi ⊥ Z: the marginal distribution of Yi does depend on Z through Di (Z), giving I1 > 0.) Since each silo applies RRε , Theorem 6.5 applies with B = log cosh(ε/2), giving Pe ≤ (n −
−B 1+e−B k ∗ ∗ 1) . Setting this ≤ n−δ requires k ≥ (1 + δ) kML where kML = ln n / (− ln 1+e2 ) = 2 ∗ ln n / CML . By Theorem F.1 (Appendix F), CML ≥ I1 /2 for all ε > 0, hence kML ≤ 2 ln n/I1 . ∗ Since I1 ≥ α by hypothesis, kML ≤ 2 ln n/α unconditionally, and k ≥ 2(1 + δ) ln n/α suffices for Pe ≤ n−δ . Remark 7.4 (Scope and generality). The two sides of the threshold theorem have different levels of generality. (a) Fano direction: The lower bound (identification is impossible for k ≲ ln n/I1 ) holds for any mechanism via Theorem 6.4 and does not depend on the channel structure. (b) Attack direction: The explicit ML upper bound in Theorem 6.5, and hence the impossibility statement in Theorem 7.3, are proved for the binary randomized-response channel. Extending the attack side to another binary or continuous-output mechanism requires a mechanism-specific likelihood or Bhattacharyya analysis (see Section 9.5 for the Gaussian abstraction). We therefore do not claim that the RR ML threshold or its constant transfers unchanged to arbitrary binary mechanisms. Corollary 7.5 (Coordination is necessary). Under the binary RR setting of Theorem 7.3, no noncoordinated mechanism collection with per-silo information I1 ≥ α > 0 can maintain non-negligible de-anonymization error once, for any δ ∈ (0, 1), k ≥

2(1 + δ) ln n . α

Equivalently, in this setting cross-silo coordination is necessary beyond the threshold scale k = Θ(ln n/I1 ).

8

Discussion: Implications for Defense Design

Theorem 7.3 establishes that no collection of non-coordinated, binary DP mechanisms can prevent de-anonymization once k exceeds k ∗ . This section sketches how the phase-transition characterization can inform the design of coordinated defenses. The constructions below are conceptual; their full security analysis (communication complexity, fault tolerance, adaptive adversary resistance) is left to future work.

8.1

The Defender’s Problem as a Constrained POMDP

We model the k-silo interaction as a partially observable Markov decision process (POMDP) from the defender’s perspective. At each time step t, a silo i must publish a response Yi ; the true target Z ∗ ∈ [n] is hidden. The defender’s information state is the adversary’s posterior belief bt = Pr[Z = z | Y1 , . . . , Yt ]. The defender seeks a policy π mapping information states to release decisions so as to minimize the adversary’s identification accuracy while satisfying a utility constraint util(π) ≥ umin . The role of k ∗ . The phase-transition result (Theorem 6.7) provides a principled coordination trigger : when the number of queried silos approaches k ∗ = log n/I1 , the posterior entropy H(Z | 11

Y1:t ) has decreased by ≈ k · I1 ≈ log n bits, meaning the adversary can identify the target with non-negligible probability. A defender who tracks t and the per-silo I1 can halt or modify releases before this threshold is crossed.

8.2

Theory-of-Mind Filtering

A Theory-of-Mind (ToM) filter [23] maintains an explicit model of the adversary’s belief. Formally, after silo i releases Yi , the filter updates: P (Yi | Z = z) bi−1 (z) , ′ ′ z ′ P (Yi | Z = z ) bi−1 (z )

bi (z) = P

a standard Bayesian update. The filter intervenes if the effective number of identifiable persons, n̂eff (bi ) = 2H(bi ) ≈ n · e−k I1 , falls below a threshold θ. Setting θ = n1−δ (for a target privacy loss δ) corresponds exactly to triggering coordination at k = (1 − δ)k ∗ , before the phase transition. Limitation. Each silo maintains only its own record; no single silo can compute bi without knowing other silos’ outputs. This motivates the coordinated approach below.

8.3

Cross-Silo Coordination via Distributed Consensus

CoDef protocol (sketch). Silos participate in a distributed consensus round to collectively estimate kreleased (the number of silos that have already responded to queries involving a given person) and to adjust their local noise levels accordingly. Concretely: 1. Commitment phase. Each silo i commits a cryptographic hash of its person-level release count ci to a shared ledger. 2. Aggregation phase. A secure aggregation protocol (e.g., SecAgg [19]) computes kreleased = P c without revealing individual ci . i i 3. Adaptation phase. When kreleased ≥ γ k ∗ for a predetermined fraction γ < 1, silos switch to ∗ (ε′ ) > k ∗ (ε), pushing the threshold a higher noise level ε′ < ε so that the post-adaptation kpost ahead. Remark 8.1 (CoDef privacy guarantee). If each silo’s adapted mechanism satisfies (ε′ , δ ′ )-DP independently with uniform parameters, then by Theorem 4.1 the joint output satisfies (kε′ , kδ ′ )XSP-DP. By operating below (1 − γ)k ∗ , the de-anonymization error probability satisfies Pe ≥ Ω(γ) (by Theorem 6.4). A full security analysis of CoDef under adaptive adversaries and Byzantine silos is an important direction for future work. The key insight is that coordination does not require sharing raw data; it requires only an aggregate count and a pre-agreed threshold derived from k ∗ .

8.4

Design Guidelines

We summarize the practical takeaways: G1 (Set k ∗ as coordination budget). System designers should compute k ∗ = log n/I1 at deployment time using the population size n and the per-silo information leakage I1 . This value serves as the total cross-silo query budget before coordination must intervene. 12

= 0.5

1.0

Error probability Pe

Phase Transition: Pe vs k/k * (ML attack, RR ) = 1.0 n = 100 n = 500 n = 2,000 n = 10,000 n = 50,000

0.8

= 2.0

n = 100 n = 500 n = 2,000 n = 10,000 n = 50,000

n = 100 n = 500 n = 2,000 n = 10,000 n = 50,000

0.6 0.4 0.2 0.0 0.0

0.5

1.0

k /k *

1.5

2.0

2.5 0.0

0.5

1.0

k /k *

1.5

2.0

2.5 0.0

0.5

1.0

k /k *

1.5

2.0

2.5

Figure 1: Phase transition: empirical Pe vs. k/k ∗ for varying n (colored curves) and ε (panels). Shaded regions show the [Fano LB, ML UB] theoretical band. Dashed vertical line at k/k ∗ = 1. G2 (Allocate budget across silos). By Lemma 6.1, mutual information accumulates linearly in k under independence. A budget-allocation rule k ∗ /k per silo (uniform) or weighted by sensitivity can be enforced via the ToM filter. G3 (Amplify Shuffling mechanisms [11, 4] reduce the effective ε by p privacy with shuffling). −1 a factor of Θ( n/k), which increases I1 and therefore k ∗ by the same factor. This is particularly effective when the query rate per silo is low. G4 (Monitor synergy, not just per-silo leakage). When Assumption A3 (conditional independence) may be violated, the ToM filter should track I(Z; Y1 , . . . , Yt ) directly rather than approximating it as kI1 . Theorem 5.1 shows that correlated mechanisms can leak synergistic information even when each silo individually satisfies I(Z; Yi ) = 0.

9

Synthetic Experiments

We validate the theory with four controlled synthetic experiments. All experiments use the binary randomized response model (RRε ) with n-person identification under a uniform prior. Code will be released upon publication.

9.1

Experiment 1: Phase Transition in Error Probability

Setup. We fix ε ∈ {0.5, 1.0, 2.0} and n ∈ {100, 500, 2000}. For each (n, ε, k), we run T = 1500 independent trials of the n-person identification game: each person p is assigned k i.i.d. attributes Zp,1:k ∼ Bern(1/2); silo i reports Yi = RRε (Zp0 ,i ) for the uniformly drawn target p0 ; the ML attacker selects the person with the highest log-likelihood. Results. Figure 1 plots Pe against the normalized threshold k/k ∗ (where k ∗ = ln n/I1 , with I1 in nats). The empirical curves exhibit the predicted sharp phase transition: Pe ≈ 1 for k ≪ k ∗ and Pe ≈ 0 for k ≫ k ∗ , with the crossing near k/k ∗ ≈ 1.5 (consistent with Theorem 6.5 which gives an upper bound; the constant factor between the Fano and ML bounds accounts for the offset). The shaded region is the theoretical band [Fano LB, ML UB]; empirical curves lie within this band throughout.

13

(a) k * vs log2 n ( = 1.0)

160 140 120 100 80 60 40

(b) k * vs 1/ 2 (n = 500)

Theory log2 n/I1 Empirical

Theory Empirical

250 200

k*

k*

k * Scaling: Theory vs Empirical

150 100 50

6

8

10

log2 n

12

14

16

0

0

1

2

1/ 2

3

4

Figure 2: k ∗ scaling laws: (a) vs. log2 n at ε = 1; (b) vs. 1/ε2 at n = 500. Black dashed: theoretical prediction; colored markers: empirical.

9.2

Experiment 2: Scaling of k ∗

Setup. We locate the empirical k ∗ by binary search for the value of k at which Pe = 0.5. We then vary (a) n ∈ {50, 100, 200, 500, 1000, 2000} at fixed ε = 1.0, and (b) ε ∈ {0.5, 0.75, 1.0, 1.5, 2.0, 2.5, 3.0} at fixed n = 500. Results. Figure 2 confirms the two scaling laws predicted by Theorem 6.7: (a) k ∗ ∝ log2 n with near-unit slope on the (log2 n, k ∗ ) plot, and (b) k ∗ ∝ 1/ε2 with near-unit slope on the (1/ε2 , k ∗ ) plot. The empirical-to-theoretical ratio is ≈ 1.5 across all settings, reflecting the constant factor between the Fano bound and the actual Pe crossing.

9.3

Experiment 3: Synergy Verification (XOR+RR)

Setup. We implement the XOR+RR construction of Theorem 5.1: Z, U ∼ Bern(1/2), X1 = U , X2 = Z ⊕ U , Yi = RRε (Xi ). Each silo individually satisfies I(Z; Yi ) = 0, but I(Z; Y1 , Y2 ) > 0. We compare (i) the exact formula 1 − Hb (2pq), (ii) the leading-order approximation ε4 /(32 ln 2), and (iii) a Monte Carlo estimate from 3 × 105 samples. Results. Figure 3 shows excellent agreement between exact and MC estimates across ε ∈ [0.1, 3.0]. The ε4 /(32 ln 2) formula achieves a ratio exact/theory ≈ 0.987 at ε = 0.2 and ≈ 0.986 at ε = 0.5 (within 1.5%), degrading to ≈ 0.920 at ε = 1.0. This confirms it as a valid leading-order approximation for ε ≲ 0.5.

9.4

Experiment 4: Bound Verification

Setup. We fix n = 500, ε = 1.0 and run T = 2500 trials per k value, checking whether the empirical Pe lies within [Fano LB, ML UB]. Results. Figure 4 confirms zero Fano LB violations (empirical Pe never falls more than 4% below the lower bound). For the ML UB, using the correct Bhattacharyya-averaging formula (n − 1) · ((1 + e−B )/2)k , the bound is trivially satisfied (capped at 1) for k < 2k ∗ and yields zero empirical violations for k ≥ 2k ∗ . The transition occurs at ≈ 1.5k ∗ empirically, consistent with the CML ≈ 2 analytic constant discussed in Theorem 6.6.

14

Synergy Verification: XOR+RR Construction (b) Small (log scale) (a) Full range Exact 1 Hb(2pq) MC estimate

0.8

10 2

0.6 0.4

10 3 10 4

0.2 0.0

Exact 4/(32ln2) MC

10 1

syn

I(Z; Y1, Y2) (bits)

1.0

10 5 0.0

0.5

1.0

1.5

2.0

2.5

3.0

0.2

0.4

0.6

0.8

1.0

1.2

1.4

Figure 3: Synergy verification: I(Z; Y1 , Y2 ) for the XOR+RR construction. (a) Full range; (b) small-ε region on log scale confirming ∆syn ≈ ε4 /(32 ln 2).

Bound verification: n = 500, = 1.0

1.0 0.8

Pe

0.6 0.4 Empirical Pe [Fano LB, ML UB] k=k*

0.2 0.0 0.0

0.5

1.0

k/k *

1.5

2.0

2.5

Figure 4: Bound verification (n = 500, ε = 1): empirical Pe (black circles) with [Fano LB, ML UB] band (blue shading). Red dashed: k = k ∗ .

9.5

Analytical Instantiation: Gaussian Mechanism (DP-SGD)

To demonstrate that the phase-transition framework extends beyond the binary RR toy model, we compute I1 and k ∗ analytically for the Gaussian mechanism—the foundation of DP-SGD [1]. Setting. Silo i releases Yi = fi (Di ) + ξi wherepfi : D → Rd has ℓ2 -sensitivity ∆ and ξi ∼ N (0, σ 2 Id ). The mechanism is (ε, δ)-DP with σ = ∆ 2 ln(1.25/δ)/ε (Gaussian DP calibration). Single-silo MI. For a scalar query d = 1 with target value z ∈ {0, 1} (binary attribute, Z ∼ Bern(1/2), shift ∆ = 1): Yi | Z = z ∼ N (z, σ 2 ). The mutual information is 
 1 I1Gauss = log 2 − Hb Φ − 2σ ≈ Substituting σ =

1 8σ 2 ln 2

bits =

1 8σ 2

nats (leading order).

p 2 ln(1.25/δ)/ε (with δ small and cδ = 2 ln(1.25/δ)): I1Gauss ≈

ε2 nats, 8 cδ

∗ kGauss (n, ε, δ) =

15

ln n I1Gauss

≈

8 cδ ln n . ε2

∗ Comparison to RR. For RRε , I1RR ≈ ε2 /8 nats, giving kRR ≈ 8 ln n/ε2 . The Gaussian ∗ ∗ , where c = 2 ln(1.25/δ) > 1 for any δ < 1.25e−1/2 ≈ 0.76. For mechanism yields kGauss = cδ · kRR δ −5 ∗ ∗ . typical δ = 10 : cδ ≈ 2 ln(125000) ≈ 23.7, so kGauss ≈ 24 kRR 2 Implication. The Θ(log n/ε ) phase-transition structure is mechanism-agnostic: it holds for any locally DP mechanism whose per-silo MI satisfies I1 = Θ(ε2 ). The Gaussian mechanism is a factor cδ more robust than binary RR (requires ≈ cδ times more silos for the attack to succeed), but the qualitative phenomenon—a sharp threshold above which de-anonymization is inevitable— persists. Experimentally validating this prediction for DP-SGD on real federated datasets (where fi is a gradient and Z indexes a training sample) is left as future work; our theory provides the quantitative prediction against which such experiments can be compared.

10

Conclusion

This paper introduces the XSP-DP threat model for cross-silo de-anonymization under local differential privacy and establishes the basic information-theoretic landscape: • The standard (kε, kδ)-DP composition bound remains valid under the person-level crosssilo adjacency (Theorem 4.1), but does not by itself reveal when de-anonymization becomes feasible. • A matching pair of Fano lower and ML upper bounds locates the de-anonymization threshold at k ∗ = Θ(log n/ε2 ) (Theorems 6.4, 6.5 and 6.7). • The XOR+RR construction shows that pure information synergy arises under DP constraints: each silo individually reveals nothing, yet two silos together leak ∆syn ≈ ε4 /(32 ln 2) (Theorem 5.1). • For binary randomized-response mechanisms, no non-coordinated collection can prevent deanonymization beyond the threshold, establishing coordination necessity (Theorem 7.3). Scope and what this paper does not do. The results here are deliberately at the Θ-level: they identify the correct scaling of the threshold and prove that the phase transition exists, but do not pin down the exact critical constant, the width of the transition window, or second-order corrections. The impossibility result applies to binary randomized response; the Fano direction is universal, but the attack-side bound for general mechanisms requires mechanism-specific analysis (the Gaussian case in Section 9.5 gives one extension). The defense constructions in Section 8 are conceptual sketches; their full security analysis under adaptive adversaries and Byzantine silos is not attempted here. Companion work. Two directions extend the baseline established in this paper. Sharp thresholds and spectral characterization: a companion paper develops exact (non-asymptotic) critical constants, second-order phase-transition analysis, and an isoperimetric / spectral bridge connecting the de-anonymization threshold to the geometry of the confusion graph induced by cross-silo observations. Coordinated defense protocols: a separate paper designs and evaluates cross-silo coordination mechanisms (dual-accountant architecture, distributed consensus) that provably keep the system below the k ∗ threshold, with system-level implementation and overhead analysis.

16

Limitations. Our analysis assumes i.i.d. binary attributes and a uniform prior (Assumption 4). If the adversary’s prior over Z is non-uniform with entropy H(Z) < ln n, the Fano bound generalizes by replacing ln n with H(Z), yielding a smaller threshold (easier attack). Extending to heterogeneous attributes, correlated silos, or adaptive adversaries is important future work. Experimentally validating the phase-transition phenomenon in realistic federated learning settings (non-synthetic datasets, gradient-based mechanisms) is a natural next step; our theory provides the quantitative prediction against which such experiments can be compared.

References [1] Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In ACM Conference on Computer and Communications Security (CCS), pages 308–318. ACM, 2016. [2] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference (TCC), pages 635–658. Springer, 2016. [3] Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. In IEEE Symposium on Security and Privacy (S&P), pages 1897–1914. IEEE, 2022. [4] Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shuffling. In Advances in Cryptology (EUROCRYPT), pages 375–403. Springer, 2019. [5] Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 202–210. ACM, 2003. [6] John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Local privacy and statistical minimax rates. In IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 429–438. IEEE, 2013. [7] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology (EUROCRYPT), pages 486–503. Springer, 2006. [8] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TCC), pages 265–284. Springer, 2006. [9] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014. [10] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In Foundations of Computer Science (FOCS), pages 51–60. IEEE, 2010. [11] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2468–2479. SIAM, 2019. 17

[12] Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In ACM Conference on Computer and Communications Security (CCS), pages 1322–1333. ACM, 2015. [13] Karan Ganju, Qi Wang, Wei Yang, Carl A. Gunter, and Nikita Borisov. Property inference attacks on fully connected neural networks using permutation invariant representations. In ACM Conference on Computer and Communications Security (CCS), pages 619–633. ACM, 2018. [14] Virgil Griffith and Christof Koch. Quantifying synergistic mutual information. In Guided Self-Organization: Inception, pages 159–190. Springer, 2014. [15] Xi He, Ashwin Machanavajjhala, and Bolin Ding. Blowfish privacy: Tuning privacy-utility trade-offs using policies. In ACM SIGMOD International Conference on Management of Data, pages 1447–1458. ACM, 2014. [16] Peter Kairouz, H Brendan McMahan, Brendan Avent, et al. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1–2):1–210, 2021. [17] Daniel Kifer and Ashwin Machanavajjhala. Pufferfish: A framework for mathematical privacy definitions. ACM Transactions on Database Systems, 39(1):1–36, 2014. [18] Joseph T Lizier, Nils Bertschinger, Jürgen Jost, and Michael Wibral. Information decomposition of target effects from multi-source interactions: Perspectives on previous, current and future work. Entropy, 20(4):307, 2018. [19] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 54 of PMLR, pages 1273–1282, 2017. [20] H Brendan McMahan, Keith Rush, and Abhradeep Guha Thakurta. Federated learning with formal differential privacy guarantees. Google AI Blog, 2022. [21] Ilya Mironov. Rényi differential privacy of the Gaussian mechanism. In Computer Security Foundations Symposium (CSF), pages 263–275. IEEE, 2017. [22] Arvind Narayanan and Vitaly Shmatikov. Robust de-anonymization of large sparse datasets. In IEEE Symposium on Security and Privacy (S&P), pages 111–125. IEEE, 2008. [23] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In IEEE Symposium on Security and Privacy (S&P), pages 3–18. IEEE, 2017. [24] Latanya Sweeney. k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10(5):557–570, 2002. [25] Paul L Williams and Randall D Beer. Nonnegative decomposition of multivariate information. arXiv preprint arXiv:1004.2515, 2010. [26] Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Analyzing the connection to overfitting. In Computer Security Foundations Symposium (CSF), pages 268–282. IEEE, 2018. 18

[27] Bin Yu. Assouad, Fano, and Le Cam. Festschrift for Lucien Le Cam: Research Papers in Probability and Statistics, pages 423–435, 1997.

A

Proof of Proposition 4.1

A.1

Pure DP case (δi = 0)

Let D ∼ps D′ : by definition of ∼ps , the two datasets differ only in the records of exactly one person p. By Assumption 1, |Di (p)| ≤ 1 for every silo i, so for each i either Di = Di′ (person p is absent or unchanged in silo i) or Di ∼adj Di′ (a single-record change in silo i). Let Sp ⊆ [k] denote the set of silos where Di ̸= Di′ . Note that Sp can include multiple silos: the adjacency relation ∼ps allows person p’s records to change in every silo simultaneously. For any measurable event S ⊆ Y1:k , apply a hybrid argument over the silos in Sp = {i1 , . . . , im }. Define intermediate datasets D(0) = D and, for j = 1, . . . , m, D(j) agrees with D′ on silos {i1 , . . . , ij } and with D on the remaining silos. For each step j, silos other than ij have identical inputs in D(j−1) and D(j) ; by independence of mechanisms (Assumption 2) and εij -DP of Mi j : Pr [M ∈ S] ≤ eεij Pr [M ∈ S]. D(j−1)

D(j)

Telescoping over j = 1, . . . , m gives Pr[M ∈ S] ≤ e

P

i∈Sp εi

D

Pr′ [M ∈ S] ≤ e

Pk

i=1 εi

D

Pr′ [M ∈ S]. D

Taking the supremum over events S and the worst case over all p and D ∼ps D′ gives ( XSP-DP.

A.2

P

i εi , 0)-

Approximate DP case

We use the standard good-set decomposition (cf. Dwork and Roth [9], Theorem 3.16). Let Pi (resp. Qi ) denote the distribution of Mi (Di ) (resp. Mi (Di′ )) for each i ∈ Sp . The (εi , δi )DP guarantee means that the “bad set”  Bi = yi : Pi (yi ) > eεi Qi (yi ) satisfies Pi (Bi ) ≤ δi . For any measurable event S ⊆ Y1:k , write G = {(y1 , . . . , yk ) : yi ∈ / Bi ∀ i ∈ Sp } for the “all-good” region. Then: P (S) = P (S ∩ G) + P (S \ G) X ≤ P (S ∩ G) + Pi (Bi ) i∈Sp

≤ P (S ∩ G) +

k X

δi .

i=1

On G, every factor satisfies the pure ratio bound Pi (yi ) ≤ eεi Qi (yi ), so by independence: P

P

P (S ∩ G) ≤ e i εi Q(S ∩ G) ≤ e i εi Q(S). P P P P Combining gives P (S) ≤ e i εi Q(S) + i δi , i.e., ( i εi , i δi )-XSP-DP. 19

B

Proof of Proposition 5.1

Setup. Let Z, U ∼ Bern(1/2) i.i.d., q = 1/(1 + eε ), p = 1 − q, and let E1 , E2 ∼ Bern(q) i.i.d., independent of Z, U . Define X1 = U , X2 = Z ⊕ U , Yi = Xi ⊕ Ei . Marginal distributions. Y1 = U ⊕ E1 . Since U ∼ Bern(1/2) and E1 ∼ Bern(q) are independent, Y1 ∼ Bern(1/2) regardless of Z. Thus Y1 ⊥ Z and I(Z; Y1 ) = 0. For Y2 = Z ⊕U ⊕E2 : conditional on any fixed z, U ∼ Bern(1/2) makes Z ⊕U ⊕E2 ∼ Bern(1/2). Hence Y2 ⊥ Z and I(Z; Y2 ) = 0. Joint observation. Y1 ⊕ Y2 = (U ⊕ E1 ) ⊕ (Z ⊕ U ⊕ E2 ) = Z ⊕ (E1 ⊕ E2 ). The XOR of independent Bern(q) bits satisfies E1 ⊕ E2 ∼ Bern(2pq) (binary symmetric channel crossover 2pq). Therefore I(Z; Y1 ⊕ Y2 ) = 1 − Hb (2pq). Since Y1 ⊕ Y2 is a deterministic function of (Y1 , Y2 ), and (Y1 , Y2 ) determines Y1 ⊕ Y2 , I(Z; Y1 , Y2 ) = 1 − Hb (2pq). 1 1 ε 1 ε 1 ε Small-ε expansion. q = 1+e ε ≈ 2 − 4 , p ≈ 2 + 4 , so 2pq = 2 2 + 4 2

1

ε 2−4

1 ε2 ε2 = 2 14 − 16 = 2− 8 .

2t 4 2 Using Hb ( 21 − t) = 1 − ln 2 + O(t ) with t = ε /8:

Hb (2pq) ≈ 1 −

2(ε2 /8)2 ε4 =1− . ln 2 32 ln 2

Thus I(Z; Y1 , Y2 ) ≈ ε4 /(32 ln 2) and ∆syn = I(Z; Y1 , Y2 ) ≈ ε4 /(32 ln 2) (since I(Z; Y1 ) = I(Z; Y2 ) = 0). Step-2 (convergence to H(Z)). As ε → ∞: q → 0, 2pq → 0, Hb (2pq) → 0, so I(Z; Y1 , Y2 ) → 1 = H(Z). Thus ∆syn → H(Z) as ε → ∞.

C

Proof of Theorem 6.4

All entropies and mutual information are in nats. Fano’s inequality for Z with n values states: H(Z | Ẑ) ≤ H(Pe ) + Pe ln(n − 1). Since Ẑ is a function of Y1:k , H(Z | Y1:k ) ≤ H(Z | Ẑ). Also, H(Z | Y1:k ) = H(Z) − I(Z; Y1:k ) = ln n − I(Z; Y1:k ). By Theorem 6.1, I(Z; Y1:k ) ≤ kI1 . Therefore: ln n − kI1 ≤ H(Pe ) + Pe ln(n − 1) ≤ 1 + Pe ln n, where H(Pe ) ≤ ln 2 < 1. Rearranging: Pe ≥ (ln n − kI1 − 1)/ ln n = 1 − (kI1 + 1)/ ln n.

D

Proof of Theorem 6.5: Bhattacharyya Averaging

p Setup. Let β = 2 q(1 − q) ∈ (0, 1) denote the Bhattacharyya coefficient between Bern(q) and Bern(1 − q). Note that β = e−B where B = log cosh(ε/2) is the Bhattacharyya distance. Pairwise error bound (fixed competitor). For fixed attributes Zp0 and Zp , let d = #{i : Zp0 ,i ̸= Zp,i } be the Hamming distance. On the d differing positions, the ML score for p and p0 are distinguished by observations Yi ∼ Bern(1 − q) (under p0 ) vs. Bern(q) (under p). On the remaining

20

k − d positions the distributions are identical. By the Bhattacharyya bound for binary hypothesis testing: Pr[Score(p) ≥ Score(p0 ) | Zp0 , Zp ] ≤ β d . iid

Averaging over random competitor. Since Zp,i ∼ Bern(1/2) independently of Zp0 ,i : EZp [Pr[·]] ≤ E[β d ] =

k Y

Pr[Zp0 ,i = Zp,i ] · 1 + Pr[Zp0 ,i ̸= Zp,i ] · β

 =

i=1

Union bound. Pe ≤

X

 EZp [Pr[·]] ≤ (n − 1)

p̸=p0

1+β 2

1+β 2

k .

k .

Threshold analysis. Setting the above ≤ n−δ : k ≥

(1 + δ) ln n − ln 1+β 2

=

(1 + δ) ln n . 2 ln 1+β

For small ε: β = e−B ≈ 1 − B ≈ 1 − ε2 /8, so   2 2 ε2 /8 ε2 I1nats ln ≈ ln = ln 1 + ≈ ≈ . 1+β 2 − ε2 /8 2 − ε2 /8 16 2 Thus the sufficient number of silos is k ≥ 2(1 + δ)k ∗ + O(1), where k ∗ = ln n/I1nats . Taking (1 + δ) → (1 + δ) in the notation: for k ≥ CML (1 + δ)k ∗ with CML → 2 as ε → 0, we have Pe ≤ n−δ . Remark D.1 (Why the analytic constant is ≈ 2). The factor CML ≈ 2 arises because the unionbound argument treats all n−1 competitors symmetrically, while in practice most competitors are far from p0 (Hamming distance ≈ k/2) and are distinguished with high probability. A refined analysis using the second-moment method would give a tighter constant; empirically Cobs ≈ 1.5 (Section 9 and theorem 6.6).

E

Partial Information Decomposition

The Williams–Beer PID [25] decomposes the joint mutual information as: X I(Z; Y1 , . . . , Yk ) = PI(α), α∈A

where the sum is over antichains α of the source lattice, and PI(α) ≥ 0 for all α. For k = 2 sources: I(Z; Y1 , Y2 ) = Red(Z; {Y1 }, {Y2 }) + UI(Z; {Y1 } \ {Y2 }) + UI(Z; {Y2 } \ {Y1 }) + Syn(Z; {Y1 , Y2 }), where Red is the redundant information shared by both sources, UI is unique information from one source, and Syn is the synergistic information only accessible from both sources jointly. The minimum mutual information (MMI) definition of redundancy:
Red(Z; {Y1 }, {Y2 }) = min I(Z; Y1 ), I(Z; Y2 ) . The synergy gap ∆syn = Syn − Red captures the net direction: positive means the joint observation reveals more than the individual sum; negative means the individual observations are redundant. 21

Remark E.1 (Definition choice). We use the MMI (minimum mutual information) definition of redundancy throughout; alternative proposals (Ibroja , Idep ) exist in the PID literature. In our XOR construction (Theorem 5.1), I(Z; Y1 ) = I(Z; Y2 ) = 0, so Red = 0 and ∆syn = Syn = I(Z; Y1 , Y2 ) > 0 regardless of which PID definition is used (all definitions agree when individual mutual informations vanish). Under Assumption 3 with positive I1 , we typically have Red > 0 and Syn > 0; the sign of ∆syn depends on the specific channel family.

F

Explicit Calculations: I1 and Cmin

F.1

Binary randomized response RRε

Let Z ∼ Bern(1/2), Y = Z ⊕ E, E ∼ Bern(q), q = 1/(1 + eε ), p = eε /(1 + eε ). Single-silo MI (in nats): I1 = H(Y ) − H(Y | Z) = ln 2 − Hb,nats (q). For small ε (using q ≈ 1/2 − ε/4 and Hb,nats (1/2 − x) = ln 2 − 2x2 + O(x4 ) with x = ε/4): Hb,nats (q) ≈ ln 2 −

ε2 , 8

I1 ≈

ε2 8

(nats).

Note: in bits, I1 ≈ ε2 /(8 ln 2); computing the ratio with mixed units (Cmin in nats, I1 in bits) yields 4 ln 2 ≈ 2.77, which is incorrect. All calculations below use nats. Channel capacity Cmin (in nats):
Cmin = DKL P (· | Z = 0) ∥ P (· | Z = 1) 1−q = (1 − 2q) · ε. = (1 − 2q) ln q For small ε: 1 − 2q = tanh(ε/2) ≈ ε/2, so Cmin ≈ ε2 /2 (nats). Ratio (consistent nats): Cmin ε2 /2 ≈ 2 = 4, I1 ε /8 confirming Theorem 6.2: Cmin /I1 → 4 as ε → 0, and Cmin /I1 ≥ 4 for all ε > 0. Bhattacharyya coefficient and distance: The Bhattacharyya coefficient between Bern(q) p and Bern(1 − q) is β = 2 q(1 − q), so B = − log β = log cosh(ε/2). Explicitly: ε/2 +e−ε/2

cosh(ε/2) = e

2

2

= 1 + ε8 + O(ε4 ). −B

Hence B = log cosh(ε/2) ≈ ε2 /8 for small ε. The averaged mixing term: − ln 1+e2 ≈ B/2 ≈ ε2 /16, consistent with CML = Θ(1). Summary of small-ε asymptotics: I1nats ≈ ε2 /8, Cmin ≈ ε2 /2, B ≈ ε2 /8, − ln((1+e−B )/2) ≈ 2 ε /16, all = Θ(ε2 ). −B

Lemma F.1 (CML ≥ I1 /2 for all ε > 0). Define CML := − ln 1+e2 where B = log cosh(ε/2). Then for all ε > 0, I1 CML ≥ , 2 ∗ where I1 = I(Z; Yi ) (in nats) for the RRε channel. Consequently, kML = ln n/CML ≤ 2 ln n/I1 .

22

Proof. Define h(ε) = 2 CML − I1 and write t = ε/2. We show h(0) = 0 and h′ (ε) > 0 for all ε > 0. Step 1: h(0) = 0. At ε = 0: cosh(0) = 1, so CML = ln(2/2) = 0 and I1 = 0. Step 2: Compute h′ (ε). Write CML = ln 2 + ln cosh(t) − ln(cosh(t) + 1). Then dCML 1 sinh(t) = · . dε 2 cosh(t)(cosh(t) + 1) Using dI1 /dε = t/(2 cosh2 (t)) from Theorem 6.2: h′ (ε) =

sinh(t) t − . cosh(t)(cosh(t) + 1) 2 cosh2 (t)

Step 3: h′ (ε) > 0. Multiply by 2 cosh2 (t)(cosh(t) + 1) > 0:
h′ (ε) > 0 ⇐⇒ 2 sinh(t) cosh(t) > t cosh(t) + 1 . Dividing both sides by cosh(t) > 0, this is equivalent to 2 sinh(t) > t(1 + sech(t)). This follows from two elementary facts valid for t > 0: (a) sinh(t) > t (since sinh(t) = t + t3 /6 + · · · > t), (b) sech(t) < 1 (since cosh(t) = 1 + t2 /2 + · · · > 1). Combining: 2 sinh(t) > 2t = t + t > t + t sech(t) = t(1 + sech(t)). Hence h′ (ε) > 0 for ε > 0, and h(0) = 0 gives h(ε) > 0 for all ε > 0, i.e., CML > I1 /2.

F.2

General (ρ, µ) model

For a signal strength ρ ∈ (0, 1] and query rate µ ∈ (0, 1] (fraction of records per silo that participate in each query; distinct from the RR flip probability q = 1/(1 + eε ) and the information lower bound α in Theorem 7.3), the leading-order formula is:   log n 2 2 2 2 ∗ I1 = Θ(µρ ε ), Cmin = Θ(µρ ε ), k =Θ . µρ2 ε2 This is the form stated in Theorem 6.7.

23