When two organizations want to train one model on customers they share (a bank with the labels, a telecom with extra features), they first have to find the shared customers. The standard tool is private set intersection, a cryptographic protocol that tells both parties which identifiers they have in common without exposing anyone else. Systems that match a centrally trained model exactly, such as SecureBoost, run this step and then train on the revealed overlap. That leaks something regulators care about: the fact that a given person is a customer of both institutions. The one fix in this literature, FLORIST, avoids the leak by training on the union of both customer lists and filling the gaps with synthetic records. That breaks the exact match with centralized training.
This note proposes a simple change that removes that trade-off for gradient-boosted trees. Keep the union, but give every row a secret-shared 0/1 weight that says "this row is truly shared." No party ever sees the weight. Multiply each row's gradient statistics by it inside the secure computation. Rows outside the intersection then contribute exactly zero to every histogram, split score, and leaf value. The trained trees are identical, up to fixed-point rounding, to centralized XGBoost trained on the true intersection, and nobody learns who is in it. The cost is extra computation on dummy rows. We borrow the routing-table idea of trading memory for path length ("stretch") to make that cost explicit and tunable. Revealing a differentially private, noisy count of the overlap lets the dummy rows be securely trimmed down to a bounded surplus.
Core Claim
The claim is that membership-hiding alignment and exact centralized parity are compatible for tree boosting. The price is compute, not accuracy, and it can be bounded. In XGBoost, split choice and leaf weights depend on the data only through sums of per-row first and second derivatives of the loss ($g_i$, $h_i$) over the rows falling in a node. Let $b_i \in \{0,1\}$ be the secret-shared membership indicator for union row $i$, and let $L$ be the rows sent left by a candidate split. The masked sums are
$$G_L = \sum_{i \in L} b_i g_i, \qquad H_L = \sum_{i \in L} b_i h_i ,$$
and these equal the unmasked sums over $L \cap I$, where $I$ is the true intersection. Every quantity XGBoost computes from them therefore coincides with the centralized computation on $I$. This includes the gain, the leaf weight $-G/(H+\lambda)$ with regularization strength $\lambda$, and the minimum-child-weight check.
Dummy rows may carry arbitrary labels and features. Unlike FLORIST's sampled features, their values never influence the model. The cost is a "stretch" factor
$$\rho = \frac{|U'|}{|I|},$$
where $U'$ is the set of rows the secure training actually processes. The protocol must process all of $U'$ even though only $|I|$ rows matter. Without trimming, $U'$ is the full union $U$. With trimming, $U'$ is $I$ plus a surplus whose size is set by a noisy count. This mirrors how Recursive SDN for Carrier Networks buys up to 93% smaller forwarding tables for 10–20% longer paths. Here, a small, formally bounded leak about $|I|$ buys a smaller $\rho$.
Research Program
The alignment stage uses a private set intersection variant that outputs the membership bit in secret-shared form rather than in the clear. Combining Private Set-Intersection with Secure Two-Party Computation builds exactly this kind of encrypted-output membership test via oblivious-transfer graph traversal. It is proven only for two parties under honest-but-curious assumptions, which is also our threat model. We take it as the method supplier. We will also implement a circuit-PSI variant built on the random-band oblivious key-value store of Near-Optimal Oblivious Key-Value Stores for Efficient PSI, PSU and Volume-Hiding Multi-Maps, which reports 12% less communication for circuit PSI than prior encodings. The union identifiers themselves come from a Diffie-Hellman private set union as in Vertical Federated Learning without Revealing Intersection Membership.
The training stage builds on the secret-sharing design of An Efficient Learning Framework for Federated XGBoost Using Secret Sharing and Distributed Optimization (MP-FedXGB). That system reaches exact parity with centralized XGBoost and runs about 13x faster than SecureBoost. It also avoids secure division by comparing cross-multiplied split scores. We change three things.
First, $g_i$ and $h_i$ are secret-shared and multiplied by the shared $b_i$ with standard multiplication triples. The label owner never holds masked gradients in the clear, because that would reveal $b_i$.
Second, the rows reaching each node are tracked as a secret-shared indicator vector, not a revealed index set. Node counts and the first-layer split are never opened, since opening them would leak partial overlap sizes. This replaces MP-FedXGB's first-layer mask with a stronger, uniform treatment.
Third, the leaf weight is computed by an exact secure reciprocal rather than MP-FedXGB's perturbed gradient descent. Iterative perturbation would reintroduce an approximation we want to rule out. We will measure whether the extra cost matters.
The trimming stage is where the routing lens earns its place. The parties jointly compute $|I|$ in shares, open a noisy version $\tilde{n} = |I| + \text{noise}$ under $\varepsilon$-differential privacy, and run oblivious sorting on the shared bits $b_i$. The protocol then keeps the first $\tilde{n} + k$ rows, with a margin $k$ chosen so that true members are dropped with negligible probability. The analysis target is a curve of stretch $\rho$ against $\varepsilon$ and failure probability, analogous to the state-versus-stretch curve in routing. We will characterize its endpoints exactly. At one end is no reveal and $\rho = |U|/|I|$. At the other is an exact size reveal and $\rho \to 1$, which matches what many circuit-PSI protocols already leak.
We will also state plainly what the method does not hide. The released trees reveal the same aggregate information about $I$ that a centrally trained model would. This is a property of centralized training, not of our protocol.
Baselines
The accuracy ceiling and cost floor is plaintext-revealed alignment followed by MP-FedXGB. It is the strongest existing lossless system in the file: identical accuracy, F1 and AUC to centralized XGBoost on GiveMeSomeCredit, with training in 44.5 s versus roughly 600 s for SecureBoost in a 4-party setup (MP-FedXGB). We rerun it on the same machines, network emulation, tree hyperparameters, and fixed-point precision as our method. Our method "beats" it on privacy by definition. On cost, success means a wall-clock and communication overhead that stays within the stretch factor $\rho$ times this baseline plus the alignment cost.
SecureBoost (SecureBoost: A Lossless Federated Learning Framework) is run the same way as the homomorphic-encryption reference. Pivot (Privacy Preserving Vertical Federated Learning for Tree-based Models) serves as the hybrid reference; it reports less than 0.1% accuracy discrepancy from fixed-point rounding. That discrepancy is the tolerance we adopt for "exact."
The strongest competitor on the actual question, hiding membership, is FLORIST. It reports that on Criteo, with 95% of labels synthetic, test AUC dropped only about 0.67% after calibration, and that spectral re-identification attack AUC fell from near 1.0 to between 0.5 and 0.57 (FLORIST). FLORIST trains neural models. For a fair comparison we apply its feature-sampling, majority-label and logit-shift recipe to the same XGBoost learner inside the same secure trainer. The union, splits, and tuning budget are identical, and the only difference is synthetic-fill versus zero-weight. Beating it means matching its attack AUC (near 0.5) while closing its AUC gap to zero relative to centralized XGBoost on the intersection. We also test whether that gap widens on regression and low-overlap splits, which FLORIST did not evaluate.
The naive reference point is salted SHA-256 matching followed by training on the revealed overlap. It anchors cost and demonstrates the leak.
Three ablations isolate the key ingredient. The first trains on the union with dummy rows zero-filled but not masked by $b_i$, to show the masking and not the union itself produces parity. The second masks but does not trim, giving the full-union cost. The third trims with exact size reveal versus DP-noised reveal, to trace the stretch-privacy curve.
Why not just…?
Why not just reveal the intersection with standard PSI or salted hashing? The identifier domains here are low-entropy, so salted hashes fall to dictionary attacks. Even proper PSI reveals membership, and FLORIST shows that membership enables re-identification with attack AUC near 1.0. The naive baseline is included precisely to reproduce this attack on our splits.
Why not just use FLORIST, since 0.67% AUC is small? This is the real threat, and we take it seriously. If FLORIST's gap stays around half a point everywhere, our contribution narrows to a guarantee rather than a practical win, bought with extra compute. Two things could still separate the methods. FLORIST's gap may grow on regression tasks such as Appliances Energy, on multi-class tasks, and at low overlap, where synthetic rows dominate. Its logit-shift calibration also has to be tuned per task, while zero-weighting needs no tuning. The matched-learner comparison across overlap ratios from 5% to 80% settles this directly. We will report the result even if FLORIST's gap turns out negligible.
Why not just centralize in a trusted enclave? Enclaves put all raw data under one hardware vendor's trust. The competing institutions targeted by Pivot and MP-FedXGB are assumed unable to accept that. Tens of millions of rows also exceed enclave memory. This is a trust argument, not an empirical one, and we do not run enclave experiments.
Why not just add differential privacy to feature histograms instead of secure computation? The survey Tree-based Models for Vertical Federated Learning: A Survey places this feature-gathering design on the lossy side of its utility–protection–cost trilemma. It also does not address membership at all, because alignment still happens in the clear. Our method spends differential privacy only on a single count, which leaves the model untouched.
Proposed Experiments
We use the tabular benchmarks from the lossless systems: GiveMeSomeCredit, Adult, Credit 1 and Credit 2, Bank Marketing, Credit Card, and Appliances Energy for regression. We add subsamples of Criteo and Avazu of 1M–5M rows. These subsamples will be reported as such, since full 45M-row secure training is outside our compute budget, and FLORIST is rerun on the same subsamples.
Each dataset is split vertically. We then generate customer lists with controlled overlap ratios $|I|/|U|$ from 0.05 to 0.8, in two- and four-party configurations.
The first decisive check is structural identity. We compare every split feature, threshold and leaf weight of our trees against centralized XGBoost trained on $I$, requiring agreement up to fixed-point rounding, and report accuracy, F1, AUC or RMSE.
The second check is privacy. We run FLORIST's spectral re-identification attack against every method's transcripts and released artifacts. We expect about 0.5 for ours and near 1.0 for revealed-alignment baselines.
The third check is cost. We measure wall-clock time, bytes and rounds per tree against the stretch factor $\rho$ for no-trim, exact-size trim, and DP trim at several $\varepsilon$. The prediction is that cost grows roughly linearly in $\rho$, because every histogram step touches each processed row once.
The idea fails if either of two things happens. One is that masked training diverges from centralized trees beyond rounding. The other is that the cost at useful $\varepsilon$ exceeds FLORIST's by more than the overlap-driven factor $\rho$ alone would predict, which would mean the secure reciprocal and hidden-node bookkeeping, not the dummy rows, dominate.
References
- Recursive SDN for Carrier Networks
- Combining Private Set-Intersection with Secure Two-Party Computation
- Near-Optimal Oblivious Key-Value Stores for Efficient PSI, PSU and Volume-Hiding Multi-Maps
- Vertical Federated Learning without Revealing Intersection Membership
- An Efficient Learning Framework for Federated XGBoost Using Secret Sharing and Distributed Optimization
- SecureBoost: A Lossless Federated Learning Framework
- Privacy Preserving Vertical Federated Learning for Tree-based Models
- Tree-based Models for Vertical Federated Learning: A Survey