pith. sign in

arxiv: 2605.26903 · v2 · pith:YHQH34XCnew · submitted 2026-05-26 · 💻 cs.CR · cs.AI

Practical Anonymous Two-Party Gradient Boosting Decision Tree

Chenyu Huang , Fan Zhang , Minxin Du , Sherman S. M. Chow , Huangxun Chen , Huaming Rao , Danqing Huang , Bo Qian
show 1 more author
Peng Chen
This is my paper

Pith reviewed 2026-06-29 16:43 UTC · model grok-4.3

classification 💻 cs.CR cs.AI
keywords anonymous gradient boostingtwo-party computationsecure machine learningcircuit private set intersectiongradient boosted decision treesvertically partitioned datahomomorphic encryptionoblivious programmable pseudorandom function
0
0 comments X

The pith

Two-party gradient boosting decision trees can be trained on vertically partitioned data while hiding shared record identifiers.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a protocol for training gradient-boosted decision trees across two parties that each hold different features of the same records, without revealing which records the parties share. It replaces standard private set intersection with an alternating dual circuit-PSI construction that uses oblivious programmable pseudorandom functions to carry state between rounds, thereby avoiding full alignment over the entire ID domain. The protocol also halves the ciphertext-packing overhead previously required when converting single-instruction multiple-data operations under ring learning-with-errors encryption. Experiments indicate the resulting scheme stays competitive in runtime and communication with earlier approaches that leak the intersection. The same ID-hiding aggregation technique is presented as reusable for other vertically partitioned analytics tasks.

Core claim

By letting the two parties alternate as receiver in successive circuit-PSI instances and propagating the outputs as shared state through oblivious programmable pseudorandom functions, the protocol performs the necessary pick-then-sum operations over local features without ever materializing a universal record alignment whose cost would scale with domain size; the same design halves the cost of the ciphertext packing step used in prior secure GBDT work, yielding an end-to-end protocol that remains competitive with leaky baselines while hiding which records are shared.

What carries the argument

Alternating dual circuit-PSI with OPPRF state propagation, which lets each party run pick-then-sum locally and carries intersection-derived state forward without domain-size alignment.

If this is right

  • The same ID-hiding aggregation can be applied to other vertically partitioned analytics beyond GBDT.
  • Secure GBDT training becomes feasible in settings such as finance and healthcare where revealing shared record identifiers is undesirable.
  • The halved ciphertext-packing technique reduces overhead in any prior secure machine-learning computation that relied on the earlier packing method.
  • Avoiding universal alignment removes the need for parties to agree on a common ID space in advance.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The alternating-receiver pattern may generalize to multi-party settings where more than two data owners must hide their intersections.
  • The state-propagation technique could be tested on other decision-tree variants or on gradient-boosted models with different splitting criteria.
  • If the OPPRF component can be replaced by a lighter primitive, the protocol's concrete cost could drop further on datasets with very large ID domains.

Load-bearing premise

The design assumes that alternating dual circuit-PSI with OPPRF state propagation can be realized without introducing new leakage or prohibitive overhead that scales with domain size, and that the halved ciphertext packing cost translates to end-to-end gains under the concrete parameter choices used in the experiments.

What would settle it

An implementation in which total communication or runtime grows linearly with the size of the ID domain, or in which the parties can still determine which records they share, would show the claimed avoidance of domain-size cost has not been achieved.

Figures

Figures reproduced from arXiv: 2605.26903 by Bo Qian, Chenyu Huang, Danqing Huang, Fan Zhang, Huaming Rao, Huangxun Chen, Minxin Du, Peng Chen, Sherman S. M. Chow.

Figure 1
Figure 1. Figure 1: Circuit-PSI asymmetry (cuckoo vs. simple hash): the receiver [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Ideal private GBDT training functionality: Outputs reveal only [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Ideal functionality and protocol of OIS entries ⟨M1⟩ B aligned to the receiver’s order. Gradients are then aggregated by pick-then-sum using secure multiplexers: ∀(z, u): P iFmux ⟨M1[zB + u, i]⟩ B l ,⟨g[i]⟩ A l  , (6) and likewise for h. This avoids generic secure matrix mul￾tiplication (which would invoke Fmul per entry) while using aligned order: ⟨M1[·, i]⟩ B l , ⟨g[i]⟩ A l refer to the same sample. Roo… view at source ↗
Figure 4
Figure 4. Figure 4: Base AnonGBDT (with Fmux-based gradient histogram aggregation and new FOIS for sample indicator updates) Complexity: If P0 holds the best split, it sends O(nℓ) bits and the round is 1; if P1 holds the best split, they invoke n 1-out-of-mB FOT (each sends O(mBℓ) bits) with total communication round of O(log n)), and n Fand (each sends O(ℓ) bits) with total communication round of O(log n+ 2). 4.2.3. Improved… view at source ↗
Figure 5
Figure 5. Figure 5: Overview of AnonGBDTOTSA (with our key contributions highlighted in red) [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Example of FastPackLWEs (n = 4, N = 4, and N = 2): The adjacent LWE ciphertexts are first packed into an RLWE ciphertext via Algorithm 1. The RLWE ciphertexts are then recursively packed into a single RLWE ciphertext via Algorithm 2. Abstraction: Conceptually, our OPPRF call expects the same ideal functionality as oblivious transfer for a sparse array [35] (with the same index domain and range). Sender￾cho… view at source ↗
Figure 7
Figure 7. Figure 7: Functionality and protocol of BinMatVec 5.4. Further Optimizations • High-precision score computation: With fixed-point pre￾cision f = 20, intermediate shares (e.g., Fmul in Eq. (2)) can exceed Z2 ℓ when n is large. We prescale inputs to [1, 2] and rescale the result, preventing overflow at negligible cost. • Gradient packing in Fmux: Filtering the (secret-shared) gradients g and h at k-th node requires th… view at source ↗
Figure 8
Figure 8. Figure 8: Ideal functionality and protocol of OOIS the number of OT used in Fmux by entry-wise packing of g and h, compared to transferring them individually. • Gradient packing in FA2H: In FA2H, we can encode gradients ⟨g⟩ A and ⟨h⟩ A within one RLWE ciphertext, i.e., bal = PN/2−1 i=0 ⟨g[i]⟩ A l Xi + PN−1 i=N/2 ⟨h[i]⟩ A l Xi (see Sec￾tion 2.2). After pick-then-sum, two LWE ciphertexts (of di￾mension N) can be direc… view at source ↗
Figure 9
Figure 9. Figure 9: AnonGBDTOTSA (with key differences to our base solution highlighted in blue) 5.5.2. Anonymous Batch Inference. In inference [21], each party Pl holds a vertically partitioned dataset (no labels), (plaintext) best splits Cl , and weight shares ⟨w⟩ A l . One party finally learns the prediction probabilities p on the joint data. Prior protocols often assume PSI-aligned inputs. Evaluation using a secure multip… view at source ↗
Figure 10
Figure 10. Figure 10: Scalability of AnonGBDTOTSA vs. Squirrel (T = 10, n = 105 , m = 10, B = 16, D = 5, and 8 threads) TABLE 6. RUNNING TIME OF AnonGBDTOTSA AND PRIOR PRIVATE (BUT “LEAKY”) SOLUTIONS (T = 10) Approach Parameters Settings Time (s) Ours n = 5 × 104 D = 4, B = 8 m0 = 8, m1 = 7 LAN 6 threads 39.0 [5] 60.0 [8] 1680.0 Ours n = 2 × 105 D = 4, B = 8 m0 = 8, m1 = 7 LAN 6 threads 96.5 [5] 111.0 [8] 448.0 Ours n = 1.4 × … view at source ↗
Figure 11
Figure 11. Figure 11: Comparison of sigmoid approximations TABLE 8. AMORTIZED BIT COMMUNICATION (COMM.) COMPLEXITY COMPARISON OF Fsigmoid BETWEEN OURS AND SQUIRREL’S Fsigmoid Ours Squirrel Comm. complexity of Fmul 288 288 · 4 Comm. complexity of two Fgreater ≈1384 − 4 log2 ⌊ f−δ 4 ⌋ −32⌊ f−δ 4 ⌋ ≈1384 # of terms in Fourier series 4 9 Comm. complexity of Fsigmoid ≈1384 − 4 log2 ⌊ f−δ 4 ⌋ −32⌊ f−δ 4 ⌋ + 288 · 6 ≈1384 + 288 · 4 ·… view at source ↗
Figure 12
Figure 12. Figure 12: Ideal functionality and protocol of BOIS 1) If (z∗, u∗) is owned by P0, S receives ⟨b∗⟩ B 1 from P0 (Line 3). Then S computes ⟨b∗⟩ B 0 = ⟨b∗⟩ B 1 ⊕Mf0[z∗B+u∗]; else S plays the sender of FOT with input of the XOR of randomly chosen r(= ⟨b∗⟩ B 0 ) and ⟨Mf1⟩ B 0 as in Line 8. 2) S plays the role of Fand with inputs of ⟨b∗⟩ B 0 , ⟨b⟩ B 0 to obtain ⟨b L⟩ B 0 , then sets ⟨b R⟩ B 0 = ⟨b L⟩ B 0 ⊕ ⟨b⟩ B 0 as Line… view at source ↗
Figure 13
Figure 13. Figure 13: Functionality and protocol of Inference 1) ∀k ∈ k, S receives ⟨b (k,c) ∗ ⟩ B 1−c from Pc and computes r c with (z (k) ∗ , u (k) ∗ ) and Mfc. Then S sets ⟨b (k,c) ∗ ⟩ B c = r c and plays the role of Fand with ⟨b (k,c) ∗ ⟩ B c and ⟨b (k,c) ⟩ B c . After obtaining ⟨b (2k,c) ⟩ B c , S computes ⟨b (2k+1,c) ⟩ B c as Lines 2–5. 2) S constructs {T} and ⟨b k,1−c ∗ ⟩ B c (∀k ∈ k) as Lines 6–11. Then S plays the rol… view at source ↗
read the original abstract

Structured data is well handled by gradient-boosted decision trees (GBDT), which are usually trained on vertically partitioned features across mutually distrustful parties. High speed and interpretability make GBDTs popular in finance and healthcare, where neural networks may fall short. Enabling secure computation for GBDTs poses unique challenges, requiring secure record alignment for comparison. Relying on private set intersection (PSI) is a de facto approach. Mistaking PSI for a safety measure actually exposes which record identifiers (IDs) are shared between the datasets. Although circuit-PSI could help, it is costly for generic uses. New ideas are needed to efficiently train in a "dark forest". Aiming to hide the IDs, we initiate the study of anonymous GBDT training on split data held by two parties. Dual circuit-PSI in our design lets the parties alternate as receiver to run pick-then-sum over local features. Via oblivious programmable pseudorandom functions, we propagate circuit-PSI outputs as shared state across runs. Avoiding universal alignment, we resolve the neglected dilemma that ID hiding incurs a cost that scales with domain size. Next, we halve the cost of ciphertext packing used to convert single-instruction multiple-data homomorphic encryption from (ring) learning with errors in prior secure GBDT (Usenix Security' 23) and related secure machine-learning computations. Comparative experiments show our protocol remains competitive with leaky approaches in efficiency. Enabling ID-hiding aggregation, our techniques can extend to other vertically partitioned analytics.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes a protocol for anonymous two-party gradient boosting decision tree (GBDT) training on vertically partitioned data. It employs dual circuit-PSI with alternating receiver roles combined with oblivious programmable pseudorandom functions (OPPRF) to propagate shared state and avoid universal alignment, thereby resolving domain-size scaling costs for ID hiding. A secondary contribution halves the ciphertext packing cost when converting SIMD homomorphic encryption based on (ring) LWE, building on prior secure GBDT work. Comparative experiments are claimed to show the protocol remains competitive in efficiency with leaky baselines, with techniques extensible to other vertically partitioned analytics.

Significance. If the efficiency and anonymity claims hold under concrete parameters, the work provides a meaningful step toward practical ID-hiding secure computation for interpretable models in regulated domains such as finance and healthcare. Explicitly tackling the domain-size dilemma for anonymous PSI-based alignment and the packing optimization are concrete technical contributions. The extension claim broadens potential impact beyond GBDT.

major comments (2)
  1. [§4 (Experiments)] §4 (Experiments): The central competitiveness claim rests on comparative runtime results, yet no parameter analysis or tables demonstrate that OPPRF invocations remain sub-linear in domain size or that the halved packing cost dominates end-to-end runtime under the reported settings and domain sizes. This directly affects whether the 'remains competitive with leaky approaches' result follows from the design.
  2. [§3 (Protocol)] §3 (Protocol): The security argument that alternating dual circuit-PSI plus OPPRF state propagation introduces no new leakage (beyond the intended anonymity) is load-bearing for the anonymity guarantee but receives only a high-level description; a concrete leakage analysis or reduction to the underlying primitives' security is needed to support the 'dark forest' training claim.
minor comments (2)
  1. [Abstract] Abstract and §1: The phrase 'comparative experiments show our protocol remains competitive' would be strengthened by naming the leaky baselines and key metrics (e.g., wall-clock time, communication) even at a high level.
  2. [§3.2] Notation: The description of 'pick-then-sum over local features' would benefit from an explicit equation or pseudocode fragment showing how circuit-PSI outputs feed into the GBDT split computation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful and constructive report. The two major comments identify areas where the current manuscript would benefit from additional detail. We address each point below and commit to revisions that strengthen the presentation without altering the core claims.

read point-by-point responses

  1. Referee: [§4 (Experiments)] §4 (Experiments): The central competitiveness claim rests on comparative runtime results, yet no parameter analysis or tables demonstrate that OPPRF invocations remain sub-linear in domain size or that the halved packing cost dominates end-to-end runtime under the reported settings and domain sizes. This directly affects whether the 'remains competitive with leaky approaches' result follows from the design.

    Authors: We agree that the experimental section would be strengthened by explicit parameter sweeps and cost breakdowns. In the revised version we will add tables and figures that (i) measure OPPRF invocation cost versus domain size for the concrete parameters used in the GBDT experiments, confirming sub-linear scaling, and (ii) isolate the contribution of the halved ciphertext-packing optimization to end-to-end runtime. These additions will make the competitiveness claim rest on documented measurements rather than aggregate timings alone. revision: yes

  2. Referee: [§3 (Protocol)] §3 (Protocol): The security argument that alternating dual circuit-PSI plus OPPRF state propagation introduces no new leakage (beyond the intended anonymity) is load-bearing for the anonymity guarantee but receives only a high-level description; a concrete leakage analysis or reduction to the underlying primitives' security is needed to support the 'dark forest' training claim.

    Authors: The current security discussion in §3 is indeed high-level. We will expand it to include an explicit leakage profile for the alternating dual circuit-PSI + OPPRF composition, showing that the only information revealed is the intended anonymity set (i.e., no additional leakage on record identifiers or feature values). Where possible we will sketch reductions to the security of the underlying circuit-PSI and OPPRF primitives. This concrete analysis will be added without changing the protocol itself. revision: yes

Circularity Check

0 steps flagged

No significant circularity; protocol built on external primitives without self-referential reductions.

full rationale

The paper presents a protocol construction for anonymous two-party GBDT training that relies on standard existing primitives (circuit-PSI, OPPRF, ring-LWE HE) and introduces dual circuit-PSI alternation plus halved ciphertext packing as design choices. No equations, fitted parameters, or load-bearing claims in the provided abstract or description reduce the anonymity or efficiency assertions to self-definitions, self-citations, or inputs by construction. The competitiveness statement rests on comparative experiments rather than a closed derivation loop. This matches the most common honest finding of a self-contained construction paper.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based solely on the abstract, the protocol rests on standard cryptographic assumptions for the security of circuit-PSI, oblivious programmable pseudorandom functions, and ring learning-with-errors homomorphic encryption; no new free parameters, invented entities, or ad-hoc axioms are explicitly introduced in the provided text.

axioms (2)
  • domain assumption Security of circuit-PSI and OPPRF primitives under the semi-honest model
    The ID-hiding property and state propagation rely on these primitives behaving as assumed.
  • domain assumption Ring-LWE based homomorphic encryption supports the claimed ciphertext packing optimization
    The halved packing cost is presented as an improvement over prior Usenix Security'23 work.

pith-pipeline@v0.9.1-grok · 5821 in / 1481 out tokens · 43471 ms · 2026-06-29T16:43:39.699742+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

69 extracted references · 2 canonical work pages

  1. [1]

    TitAnt: Online real-time transaction fraud detection in Ant Financial,

    S. Cao, X. Yang, C. Chen, J. Zhou, X. Li, and Y . Qi, “TitAnt: Online real-time transaction fraud detection in Ant Financial,”Proc. VLDB Endow., vol. 12, no. 12, pp. 2082–2093, 2019

    2082

  2. [2]

    Where medical statistics meets artificial intelligence,

    D. J. Hunter and C. Holmes, “Where medical statistics meets artificial intelligence,”New England Journal of Medicine, vol. 389, no. 13, pp. 1211–1219, 2023

    2023

  3. [3]

    Model ensem- ble for click prediction in Bing search ads,

    X. Ling, W. Deng, C. Gu, H. Zhou, C. Li, and F. Sun, “Model ensem- ble for click prediction in Bing search ads,” inWWW (Companion), 2017, pp. 689–698

    2017

  4. [4]

    SoK: Cryptographic neural-network computation,

    L. K. L. Ng and S. S. M. Chow, “SoK: Cryptographic neural-network computation,” inS&P, 2023, pp. 497–514

    2023

  5. [5]

    Squirrel: A scalable secure two-party computation framework for training gradient boosting decision tree,

    W. Lu, Z. Huang, Q. Zhang, Y . Wang, and C. Hong, “Squirrel: A scalable secure two-party computation framework for training gradient boosting decision tree,” inUSENIX Security, 2023, pp. 6435– 6451

    2023

  6. [6]

    PriVDT: An efficient two-party cryptographic framework for vertical decision trees,

    H. Chen, H. Li, Y . Wang, M. Hao, G. Xu, and T. Zhang, “PriVDT: An efficient two-party cryptographic framework for vertical decision trees,”IEEE Trans. Inf. Forensics Secur., vol. 18, pp. 1006–1021, 2023

    2023

  7. [7]

    Large-scale secure XGB for vertical federated learn- ing,

    W. Fang, D. Zhao, J. Tan, C. Chen, C. Yu, L. Wang, L. Wang, J. Zhou, and B. Zhang, “Large-scale secure XGB for vertical federated learn- ing,” inCIKM, 2021, pp. 443–452

    2021

  8. [8]

    Privacy preserv- ing vertical federated learning for tree-based models,

    Y . Wu, S. Cai, X. Xiao, G. Chen, and B. C. Ooi, “Privacy preserv- ing vertical federated learning for tree-based models,”Proc. VLDB Endow., vol. 13, no. 11, pp. 2090–2103, 2020

    2090

  9. [9]

    Efficient private matching and set intersection,

    M. J. Freedman, K. Nissim, and B. Pinkas, “Efficient private matching and set intersection,” inEUROCRYPT, 2004, pp. 1–19

    2004

  10. [10]

    Efficient batched oblivious PRF with applications to private set intersection,

    V . Kolesnikov, R. Kumaresan, M. Rosulek, and N. Trieu, “Efficient batched oblivious PRF with applications to private set intersection,” inCCS, 2016, pp. 818–829

    2016

  11. [11]

    Unique in the shopping mall: On the reidentifiability of credit card metadata,

    Y .-A. D. Montjoye, L. Radaelli, V . K. Singh, and A. S. Pentland, “Unique in the shopping mall: On the reidentifiability of credit card metadata,”Science, vol. 347, no. 6221, pp. 536–539, 2015

    2015

  12. [12]

    On deploying secure computing: Private intersection-sum-with-cardinality,

    M. Ion, B. Kreuter, A. E. Nergiz, S. Patel, S. Saxena, K. Seth, M. Raykova, D. Shanahan, and M. Yung, “On deploying secure computing: Private intersection-sum-with-cardinality,” inEuroS&P, 2020, pp. 370–389

    2020

  13. [13]

    Efficient circuit-based PSI with linear communication,

    B. Pinkas, T. Schneider, O. Tkachenko, and A. Yanai, “Efficient circuit-based PSI with linear communication,” inEUROCRYPT Part III, 2019, pp. 122–153

    2019

  14. [14]

    VOLE-PSI: Fast OPRF and circuit- PSI from vector-OLE,

    P. Rindal and P. Schoppmann, “VOLE-PSI: Fast OPRF and circuit- PSI from vector-OLE,” inEUROCRYPT Part II, 2021, pp. 901–930

    2021

  15. [15]

    Blazing fast PSI from improved OKVS and subfield VOLE,

    S. Raghuraman and P. Rindal, “Blazing fast PSI from improved OKVS and subfield VOLE,” inCCS, 2022, pp. 2505–2517

    2022

  16. [16]

    PSI- Stats: Private set intersection protocols supporting secure statistical functions,

    J. H. M. Ying, S. Cao, G. S. Poh, J. Xu, and H. W. Lim, “PSI- Stats: Private set intersection protocols supporting secure statistical functions,” inACNS, 2022, pp. 585–604

    2022

  17. [17]

    Private set operations from oblivious switching,

    G. Garimella, P. Mohassel, M. Rosulek, S. Sadeghian, and J. Singh, “Private set operations from oblivious switching,” inPKC Part II, 2021, pp. 591–617

    2021

  18. [18]

    Secure-computation-friendly pri- vate set intersection from oblivious compact graph evaluation,

    J. P. K. Ma and S. S. M. Chow, “Secure-computation-friendly pri- vate set intersection from oblivious compact graph evaluation,” in AsiaCCS, 2022, pp. 1086–1097

    2022

  19. [19]

    CrypTFlow2: Practical 2-party secure inference,

    D. Rathee, M. Rathee, N. Kumar, N. Chandran, D. Gupta, A. Rastogi, and R. Sharma, “CrypTFlow2: Practical 2-party secure inference,” in CCS, 2020, pp. 325–342

    2020

  20. [20]

    Efficient homomorphic conversion between (ring) LWE ciphertexts,

    H. Chen, W. Dai, M. Kim, and Y . Song, “Efficient homomorphic conversion between (ring) LWE ciphertexts,” inACNS, 2021, pp. 460– 479

    2021

  21. [21]

    Let’s stride blindfolded in a forest: Sublinear multi-client decision trees evaluation,

    J. P. K. Ma, R. K. H. Tai, Y . Zhao, and S. S. M. Chow, “Let’s stride blindfolded in a forest: Sublinear multi-client decision trees evaluation,” inNDSS, 2021

    2021

  22. [22]

    XGBoost: A scalable tree boosting system,

    T. Chen and C. Guestrin, “XGBoost: A scalable tree boosting system,” inKDD, 2016, pp. 785–794

    2016

  23. [23]

    LightGBM: A highly efficient gradient boosting decision tree,

    G. Ke, Q. Meng, T. Finley, T. Wang, W. Chen, W. Ma, Q. Ye, and T. Liu, “LightGBM: A highly efficient gradient boosting decision tree,” inNeurIPS, 2017, pp. 3146–3154

    2017

  24. [24]

    ABY - A framework for efficient mixed-protocol secure two-party computation,

    D. Demmler, T. Schneider, and M. Zohner, “ABY - A framework for efficient mixed-protocol secure two-party computation,” inNDSS, 2015

    2015

  25. [25]

    Efficient multiparty protocols using circuit randomiza- tion,

    D. Beaver, “Efficient multiparty protocols using circuit randomiza- tion,” inCRYPTO, 1991, pp. 420–432

    1991

  26. [26]

    Secure computation with fixed-point numbers,

    O. Catrina and A. Saxena, “Secure computation with fixed-point numbers,” inFC, 2010, pp. 35–50

    2010

  27. [27]

    Improved garbled circuit building blocks and applications to auctions and computing minima,

    V . Kolesnikov, A. Sadeghi, and T. Schneider, “Improved garbled circuit building blocks and applications to auctions and computing minima,” inCANS, 2009, pp. 1–20

    2009

  28. [28]

    How to exchange secrets with oblivious transfer,

    M. O. Rabin, “How to exchange secrets with oblivious transfer,” IACR Cryptol. ePrint Arch. 2005/187, 2005

    2005

  29. [29]

    Ferret: Fast extension for correlated OT with small communication,

    K. Yang, C. Weng, X. Lan, J. Zhang, and X. Wang, “Ferret: Fast extension for correlated OT with small communication,” inCCS, 2020, pp. 1607–1626

    2020

  30. [30]

    Fully homomorphic encryption from ring-lwe and security for key dependent messages,

    Z. Brakerski and V . Vaikuntanathan, “Fully homomorphic encryption from ring-lwe and security for key dependent messages,” inCRYPTO, 2011, pp. 505–524

    2011

  31. [31]

    Security and composition of multiparty cryptographic protocols,

    R. Canetti, “Security and composition of multiparty cryptographic protocols,”J. Cryptol., vol. 13, no. 1, pp. 143–202, 2000

    2000

  32. [32]

    Secure softmax/sigmoid for machine-learning computation,

    Y . Zheng, Q. Zhang, S. S. M. Chow, Y . Peng, S. Tan, L. Li, and S. Yin, “Secure softmax/sigmoid for machine-learning computation,” inACSAC, 2023, pp. 463–476

    2023

  33. [33]

    SHAFT: Secure, handy, accurate, and fast transformer inference,

    A. Y . L. Kei and S. S. M. Chow, “SHAFT: Secure, handy, accurate, and fast transformer inference,” inNDSS, 2025

    2025

  34. [34]

    Communication-efficient secure logistic regression,

    A. Amit, P. Stanislav, R. Mariana, S. Phillipp, and S. Karn, “Communication-efficient secure logistic regression,” inEuroS&P, 2024, pp. 440–467

    2024

  35. [35]

    Are you the one to share? Secret transfer with access structure,

    Y . Zhao and S. S. M. Chow, “Are you the one to share? Secret transfer with access structure,”Proc. Priv. Enhancing Technol., vol. 2017, no. 1, pp. 149–169, 2017

    2017

  36. [36]

    Federated transformer: Multi- party vertical federated learning on practical fuzzily linked data,

    Z. Wu, J. Hou, Y . Diao, and B. He, “Federated transformer: Multi- party vertical federated learning on practical fuzzily linked data,” in NeurIPS, 2024

    2024

  37. [37]

    Distributed learning of deep neural network over multiple agents,

    O. Gupta and R. Raskar, “Distributed learning of deep neural network over multiple agents,”J. Netw. Comput. Appl., vol. 116, pp. 1–8, 2018

    2018

  38. [38]

    Cheetah: Lean and fast secure two-party deep neu- ral network inference,

    SecretFlow, “Cheetah: Lean and fast secure two-party deep neu- ral network inference,” https://github.com/secretflow/spu/tree/main/ libspu/mpc/cheetah, 2024

    2024

  39. [39]

    Homomorphic encryption for arithmetic of approximate numbers,

    J. H. Cheon, A. Kim, M. Kim, and Y . S. Song, “Homomorphic encryption for arithmetic of approximate numbers,” inASIACRYPT Part I, 2017, pp. 409–437

    2017

  40. [40]

    Microsoft SEAL (release 4.1),

    K. Laine, “Microsoft SEAL (release 4.1),” https://github.com/ Microsoft/SEAL, 2023, Microsoft Research, Redmond, W A, USA

    2023

  41. [41]

    LIBSVM data: Classification (binary class),

    C.-J. Lin, “LIBSVM data: Classification (binary class),” https://www. csie.ntu.edu.tw/∼cjlin/libsvmtools/datasets/binary.html, 2024

    2024

  42. [42]

    eXtreme gradient boosting,

    D. D. M. L. Community, “eXtreme gradient boosting,” https://github. com/dmlc/xgboost, 2024

    2024

  43. [43]

    Efficient permu- tation correlations and batched random access for two-party compu- tation,

    S. Peceny, S. Raghuraman, P. Rindal, and H. Shah, “Efficient permu- tation correlations and batched random access for two-party compu- tation,” inPKC Part IV, 2025, pp. 76–109

    2025

  44. [44]

    Private matching for compute,

    P. Buddhavarapu, A. Knox, P. Mohassel, S. Sengupta, E. Taubeneck, and V . Vlaskin, “Private matching for compute,” IACR Cryptol. ePrint Arch. 2020/599, 2020

    2020

  45. [45]

    Can you find the one for me?

    Y . Zhao and S. S. M. Chow, “Can you find the one for me?” inWPES, co-located with CCS, 2018, pp. 54–65

    2018

  46. [46]

    Privacy preserving data mining,

    Y . Lindell and B. Pinkas, “Privacy preserving data mining,” in CRYPTO, 2000, pp. 36–54

    2000

  47. [47]

    Understanding privacy risk of publishing decision trees,

    Z. Zhu and W. Du, “Understanding privacy risk of publishing decision trees,” inDBSec, 2010, pp. 33–48

    2010

  48. [48]

    SecureXGB: A secure and efficient multi-party protocol for vertical federated XGBoost,

    Z. Han, X. Cheng, W. Zhao, J. Fu, Z. He, and S. Su, “SecureXGB: A secure and efficient multi-party protocol for vertical federated XGBoost,”SIGMOD, vol. 3, no. 1, pp. 1–26, 2025

    2025

  49. [49]

    Efficient de- cision tree training with new data structure for secure multi-party computation,

    K. Hamada, D. Ikarashi, R. Kikuchi, and K. Chida, “Efficient de- cision tree training with new data structure for secure multi-party computation,”Proc. Priv. Enhancing Technol, pp. 343–364, 2023

    2023

  50. [50]

    Securely training decision trees efficiently,

    D. Bhardwaj, S. Saravanan, N. Chandran, and D. Gupta, “Securely training decision trees efficiently,” inCCS, 2024, pp. 4673–4687

    2024

  51. [51]

    Ents: An efficient three-party training framework for decision trees by communication optimization,

    G. Lin, W. Han, W. Ruan, R. Zhou, L. Song, B. Li, and Y . Shao, “Ents: An efficient three-party training framework for decision trees by communication optimization,” inCCS, 2024, pp. 4376–4390

    2024

  52. [52]

    SecureBoost: A lossless federated learning framework,

    K. Cheng, T. Fan, Y . Jin, Y . Liu, T. Chen, D. Papadopoulos, and Q. Yang, “SecureBoost: A lossless federated learning framework,” IEEE Intell. Syst., vol. 36, no. 6, pp. 87–98, 2021

    2021

  53. [53]

    VF2Boost: Very fast vertical federated gradient boosting for cross- enterprise learning,

    F. Fu, Y . Shao, L. Yu, J. Jiang, H. Xue, Y . Tao, and B. Cui, “VF2Boost: Very fast vertical federated gradient boosting for cross- enterprise learning,” inSIGMOD, 2021, pp. 563–576

    2021

  54. [54]

    Label inference attacks against vertical federated learning,

    C. Fu, X. Zhang, S. Ji, J. Chen, J. Wu, S. Guo, J. Zhou, A. X. Liu, and T. Wang, “Label inference attacks against vertical federated learning,” inUSENIX Security, 2022, pp. 1397–1414

    2022

  55. [55]

    Eliminating label leakage in tree- based vertical federated learning,

    H. Takahashi, J. Liu, and Y . Liu, “Eliminating label leakage in tree- based vertical federated learning,” arXiv:2307.10318, 2023

    work page arXiv 2023

  56. [56]

    Practical secure decision tree learning in a teletreatment application,

    S. de Hoogh, B. Schoenmakers, P. Chen, and H. op den Akker, “Practical secure decision tree learning in a teletreatment application,” inFC, 2014, pp. 179–194

    2014

  57. [57]

    Secure training of decision trees with continuous attributes,

    M. Abspoel, D. Escudero, and N. V olgushev, “Secure training of decision trees with continuous attributes,”Proc. Priv. Enhancing Technol., vol. 2021, no. 1, pp. 167–187, 2021

    2021

  58. [58]

    SiGBDT: Large-scale gradient boosting decision tree training via function secret sharing,

    Y . Jiang, F. Mei, T. Dai, and Y . Li, “SiGBDT: Large-scale gradient boosting decision tree training via function secret sharing,” inAsi- aCCS, 2024, pp. 274–288

    2024

  59. [59]

    NodeGuard: A highly efficient two-party computation framework for training large-scale gradient boosting decision tree,

    T. Dai, Y . Jiang, Y . Li, and F. Mei, “NodeGuard: A highly efficient two-party computation framework for training large-scale gradient boosting decision tree,” inDeep Learning Security and Privacy (DLSP) Workshop, co-located with S&P, 2024, pp. 95–103

    2024

  60. [60]

    SoK: Privacy-preserving collaborative tree-based model learning,

    S. Chatel, A. Pyrgelis, J. R. Troncoso-Pastoriza, and J. Hubaux, “SoK: Privacy-preserving collaborative tree-based model learning,” Proc. Priv. Enhancing Technol., vol. 2021, no. 3, pp. 182–203, 2021

    2021

  61. [61]

    Vertical federated learning without revealing intersection member- ship,

    J. Sun, X. Yang, Y . Yao, A. Zhang, W. Gao, J. Xie, and C. Wang, “Vertical federated learning without revealing intersection member- ship,” arXiv:2106.05508, 2021

    work page arXiv 2021

  62. [62]

    OpenVFL: A vertical federated learn- ing framework with stronger privacy-preserving,

    Y . Yang, X. Chen, Y . Pan, J. Shen, Z. Cao, X. Dong, X. Li, J. Sun, G. Yang, and R. H. Deng, “OpenVFL: A vertical federated learn- ing framework with stronger privacy-preserving,”IEEE Trans. Inf. Forensics Secur., vol. 19, pp. 9670–9681, 2024

    2024

  63. [63]

    Improved multiplication triple generation over rings via RLWE-based AHE,

    D. Rathee, T. Schneider, and K. K. Shukla, “Improved multiplication triple generation over rings via RLWE-based AHE,” inCANS, 2019, pp. 347–359

    2019

  64. [64]

    (Leveled) fully ho- momorphic encryption without bootstrapping,

    Z. Brakerski, C. Gentry, and V . Vaikuntanathan, “(Leveled) fully ho- momorphic encryption without bootstrapping,”ACM Trans. Comput. Theory, vol. 6, no. 3, pp. 13:1–13:36, 2014

    2014

  65. [65]

    Linear private set union from multi-query reverse private membership test,

    C. Zhang, Y . Chen, W. Liu, M. Zhang, and D. Lin, “Linear private set union from multi-query reverse private membership test,” inUSENIX Security, 2023, pp. 337–354. Appendix A. Optimizations in Sigmoid A.1. Secure Decimal Multiplication for Trigono- metric Functions Fmul relies on Beaver triples [25] fora·b=cin secret shares, which can be efficiently impl...

    2023

  66. [66]

    ThenScomputes⟨b ∗⟩B 0 =⟨b ∗⟩B 1 ⊕fM0[z∗B+u ∗]; elseSplays the sender ofF OT with input of the XOR of randomly chosenr(=⟨b ∗⟩B 0 ) and⟨ fM1⟩B 0 as in Line 8

    If(z ∗, u∗)is owned byP 0,Sreceives⟨b ∗⟩B 1 fromP 0 (Line 3). ThenScomputes⟨b ∗⟩B 0 =⟨b ∗⟩B 1 ⊕fM0[z∗B+u ∗]; elseSplays the sender ofF OT with input of the XOR of randomly chosenr(=⟨b ∗⟩B 0 ) and⟨ fM1⟩B 0 as in Line 8. 2)Splays the role ofF and with inputs of⟨b ∗⟩B 0 ,⟨b⟩ B 0 to obtain⟨b L⟩B 0 , then sets⟨b R⟩B 0 =⟨b L⟩B 0 ⊕ ⟨b⟩B 0 as Line 11. To prove th...

  67. [67]

    For treet∈ T t,Splays the role ofF sigmoid,F mul, and Fmux with input⟨b (1,i)⟩B 0 and⟨y i⟩A 0 to derive the gradients ⟨g(1,i)⟩A 0 ,⟨h (1,i)⟩A 0 , fori∈ {0,1}as Lines 5–6. 3)∀internal nodekof treet, ifkis a root/left node,Splays the role ofF BinMatVec alternately to obtain ⟨˜g(k,i)⟩A 0 ||⟨˜h(k,i)⟩A 0 fori∈ {0,1}, which are concatenated as Line 13; elseScal...

  68. [68]

    For treet,Splays the role ofF div with inputs ⟨g(k,0)⟩A 0 ,⟨h (k,0)⟩A 0 to obtain the weight⟨w⟩ A 0 as Line 22

  69. [69]

    To prove the simulation is indistinguishable from the real protocol, we consider the following hybrids

    For treet,Splays the role ofF mux with inputs ⟨b(k,i)⟩B 0 ,⟨w[k]⟩ A 0 to update⟨ ˜yi⟩A 0 (i∈ {0,1}) as Line 23. To prove the simulation is indistinguishable from the real protocol, we consider the following hybrids. Hybrid0. The same as the real protocol. Hybrid1. Lines 2–3 (Π OTSA GBDT) use replacedF CPSI. Hybrid2. Lines 5–6 use replacedF sigmoid,F mul,F...

    2026