ARTIFACT EVALUATED
ARTIFACT EVALUATED
ARTIFACT EVALUATED
AVAILABLE
FUNCTIONAL
REPRODUCED
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∗ and Peng Chen∗ {chenyuhuang, zxfanzhang}@tencent.com, [email protected]
arXiv:2605.26903v1 [cs.CR] 26 May 2026
∗ Tencent, † Hong Kong Polytechnic University, ‡ Chinese University of Hong Kong, § HKUST-GZ
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 circuitPSI 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.
1. Introduction Structured data is well served by gradient-boosted decision trees (GBDT), an interpretable, state-of-the-art learner for domains like finance [1], healthcare [2], advertising [3], and beyond, even amid the rise of deep neural networks [4]. However, privacy regulations preclude plaintext centralization across distrustful silos, motivating private vertical train¶ Co-first Authors, Co-corresponding Minxin Du is supported in part by the HK PolyU Start-up Fund (P0052722). His work is partly done at CUHK, supported by Direct Grant (4055238). Sherman Chow is supported in part by the General Research Funds (CUHK 14210825, 14210621) from the Research Grant Council, the Hong Kong Special Administrative Region of the People’s Republic of China; and by Direct Grant (4055238) and the Strategic Impact Enhancement Fund (3135517) from CUHK. Chow contributes to scholarly work, but administrative, business, or compliance matters fall outside his purview.
ing on disjoint feature sets over overlapping populations. Even with secure multiparty computation, different datasets seldom align record-by-record, for example, a bank seeking payment-provider signals often finds that rosters that only partially overlap and differ in order (specifically, row i on one side need not be the same as row i on the other). Reconciling them requires privately computing the identifier (e.g., national ID) intersection and agreeing on a common order, and the mapping must be refreshed as rosters churn. Most secure two-party protocols [5], [6], [7], [8] address this by running private set intersection (PSI) [9], [10] for pre-alignment, a setup step that determines which identifiers are shared across the datasets while hiding others. Although common, revealing intersection membership is sensitive: linking credit-card transaction IDs to advertising data enables re-identification [11], [12], and revealing which patients two hospitals share can leak geographic or medical information, e.g., oncology referrals in a small suburb. Noting that GBDT needs only features, not identifiers, we seek to keep all IDs and their alignment private throughout collaborative training, a regime we call anonymous training.
1.1. Securely Sewing Metadata via Secret Match Shielding identifiers entirely, we introduce the first anonymous two-party GBDT protocol that never reveals them, intersecting or not. Matching that goal, circuitPSI [13], [14], [15] is a natural starting point because it can evaluate arbitrary circuits on payloads attached to the hidden intersection. Current uses, however, are limited to order-independent aggregates like sums [12] or simple statistics [16]; even counting the intersection size incurs ∼20× more cost than vanilla PSI [17], let alone modeling an entire GBDT as an arithmetic circuit. The difficulty stems from an optimization in circuit-PSI: the parties employ asymmetric hashing. The receiver inserts each ID into a cuckoo table with one bucket per ID, and a stash handles overflows from collisions. In contrast, the sender places each ID in all corresponding buckets by simple hashing, creating a one-to-many mapping. PSI then reduces to per-bucket private set membership (PSM) testing [18]. Such asymmetry poses two challenges for GBDT training: I) Gradient histograms: Each party holds n samples with m real-valued features, discretized into an mB × n binary matrix M (B bins per feature). Each node maintains a
sample indicator b ∈ {0, 1}n tracking which samples reach it. Gradients are filtered by b and aggregated by multiplying M to form histograms. The receiver, knowing the one-toone mapping from columns to gradients, can run a secure two-party functionality FBinMatVec for binary matrix-vector multiplication to multiply M with gradient shares. However, the sender cannot because one-to-many hashing obscures which gradient aligns to which column. II) Indicator synchronization: A Boolean indicator vector tracks which samples reach each node, and PSI-based schemes start with 1n . To keep it secret while allowing efficient local updates (Section 4.1), Squirrel resorts to ANDsharing [5], which is leaky in this setting. More importantly, the indicator synchronization for children fails when the sender owns the split due to the one-to-many mapping. These challenges prompt a broader question: “Can we perform order-dependent computation on circuit-PSI outputs without generic secure multiparty computation?” The techniques here answer affirmatively, enabling practical anonymous GBDT and informing other secure computations.
1.2. Technical Overview Base solution: Circuit-PSI [13], [14], [15] enables oblivious processing of payloads attached to intersecting IDs. In our base design, the sender attaches its binary feature matrix as the payload. After PSI, the matrix is secret-shared and aligned with the joint ID list. Gradient histograms are then built by a pick-then-sum procedure with secure multiplexer Fmux [19]; this entails O(nmB) oblivious transfers (OTs). To update the per-node sample indicator, we introduce a new OT-based oblivious indicator synchronization (OIS) protocol. If the receiver owns the best split, it directly shares one column of its feature matrix; otherwise, the two parties execute a 1-out-of-mB OT for every row so that the sender can retrieve the required column without revealing the index. In either case, secure AND [19] and (plaintext) string XOR then derive the children’s indicator shares (Section 4.2.2). While feasible and anonymous, the base design is OT-heavy. Dual-circuit-PSI (which “symmetrizes” alignment): Our final design, with codename OTSA, reduces OTs and symmetrizes alignment via a new dual-circuit-PSI framework: two circuit-PSI instances run with swapped roles, so each party learns an ID-to-bucket mapping once. No feature matrix needs to be sent as a payload; both remain local, and gradient aggregation switches from Fmux to communication-friendly FBinMatVec . We use AnonGBDT to refer to both the base design and the final extension. Fast ciphertext packing (halving costs): Our instantiation uses homomorphic encryption instantiated from the learning-with-error (LWE) assumption and its ring variant, ring LWE (RLWE) assumption.1 In FBinMatVec , gradient shares are converted to RLWE ciphertexts, homomorphically picked-and-summed, and output as multiple LWE ciphertexts that are packed into one RLWE ciphertext. Our 1. Hereinafter, we may use shorthand LWE/RLWE to refer to ciphertexts produced by an encryption scheme under the LWE/RLWE assumption.
FastPackLWEs subroutine (Section 5.2) first packs each adjacent LWE pair directly into one RLWE (eliminating lifting), then recursively merges RLWEs. This streamlines the raw LWEDimLift-then-PackLWEs approach [5], hence halving inputs and runtime, where the former is for lifting an LWE ciphertext to a larger lattice dimension and the latter is for homomorphically merging LWE ciphertexts into one RLWE ciphertext that decrypts to a related polynomial [20]. Batched OPPRF-based OIS: Keeping both feature matrices local invalidates the row-wise OT-based OIS in the base protocol. An OIS based on oblivious programmable pseudorandom function (OPPRF) is introduced (Section 5.3): the split owner programs an OPPRF so the counterparty obtains exact assignment shares for all its cuckoo buckets. Levelwise batching yields a batched variant FBOIS with O(D) cost instead of O(2D ) for tree depth D. We present independent optimizations (Sections 4.2.3 and 5.4), e.g., better sigmoid approximation, gradient packing, and lightweight argmax, which also accelerate Squirrel. These refinements help the dual-circuit-PSI design outperform the base design and match non-anonymous Squirrel, despite partial per-instance recomputation, e.g., gradients. Our main contributions are summarized below. 1) To our knowledge, AnonGBDT is the first two-party protocol that enables anonymous GBDT training (and inference [21]). AnonGBDT builds on circuit-PSI [14], [15], which keeps every common ID hidden and maintains private alignment throughout training, for anonymity that prior PSI-based approaches did not provide. 2) Circuit-PSI asymmetric hashing (cuckoo vs. simple) creates two challenges, namely, gradient aggregation and indicator synchronization. In our base design, the sender’s feature matrix is carried as a payload. Gradients are selected via the secure multiplexer [19], and indicators are reconciled via a custom OIS protocol. Both are functional yet OT-intensive. 3) AnonGBDTOTSA uses a new dual-circuit-PSI framework to symmetrize the workflow. Both parties now build histograms with the OT-free FBinMatVec , optimized by our FastPackLWEs subroutine. Since the base OIS no longer applies, we propose an OPPRF-based variant with level-wise batching, which reduces communication logarithmically. 4) We evaluate on real-world and synthetic datasets. All executable code is open source2 . AnonGBDTOTSA is up to 20× faster and 44× lighter than the base version, and it matches Squirrel under local area network (LAN) settings. Its runtime and traffic never exceed 1.8× those of Squirrel for wide area networks (WAN), while providing strictly stronger privacy. (We exclude the naı̈ve baseline that embeds the entire GBDT training in circuit-PSI, which is orders of magnitude slower.)
2. Preliminaries |S| is the size of the set S . Sampling from a finite set S or a distribution D is denoted by x ←$ S or x ← D. ⊥ is 2. https://zenodo.org/records/17373936
TABLE 1. N OTATIONS WITH DESCRIPTIONS Symbol B ⟨·⟩A l , ⟨·⟩l J·K IDl , Xl nl , ml Ml B y T D z ∗ , u∗ q g(k) , h(k) b(k) w ql g(k,l) , h(k,l) b(k,l) Tlch , Tlsh
Description Pl ’s arithmetic and boolean shares RLWE HE-encrypted variable Sample IDs and features owned by party Pl Number of samples and features in Xl Discrete feature binary matrix of Xl Number of bins in Ml Label set Number of trees Depth of tree Best split: u∗ -th bin of z∗ -th feature Result of circuit-PSI 1st and 2nd order of gradients of node k Sample indicator of node k Leaf weight Result of l-th circuit-PSI Gradients of node k based on q(l) Sample indicator of node k based on q (l) Cuckoo and simple hash tables of l-th circuit-PSI
the error symbol. The computational and statistical security parameters are λ and κ, respectively. The indicator function 1{x} equals 1 if x is true; 0, otherwise. Bold lowercase letters denote vectors (e.g., a) and bold uppercase letters denote matrices (e.g., M). For indices, a[i] is the i-th entry of a, M[i] (or Mi ) is the i-th row of M, and M[i, j] is the entry in row i, column j . Polynomials are written as b a, where b a[i] is its i-th coefficient. Define the polynomial ring R = Z[X]/(X N + 1), where N is a power of 2. For a modulus Q ∈ Z, set RQ = R/QR = ZQ [X]/(X N + 1). Table 1 lists all notations.
regularization on leaf weights and γ ≥ 0 the complexity penalty per split, the split gain (or “score”) Lsp is " P 2 2 2 # P P 1 i∈IL g[i] i∈IR g[i] i∈I g[i] P +P −P −γ. 2 i∈IL h[i] + α i∈IR h[i] + α i∈I h[i] + α (2) The best split maximizes Lsp over all candidates ϕ for all z . Histogram-based Search: Exhaustive threshold scanning per feature is costly. We apply histogram binning [22], [23] to discretize each feature into B ordered bins. Let M ∈ {0, 1}Bm×n be the “one-hot bin indicator” matrix, where M[zB + u, i] = 1 iff sample i falls into bin u of feature z .3 Aggregating {g[i], h[i]} into per-bin histograms supports efficient split evaluation by scanning bin boundaries, and the optimal one is denoted by (z⋆ , u⋆ ). For convenience, we f ∈ {0, 1}Bm×n pre-compute an exclusive-prefix matrix M W f with rows M[zB + u, i] = v≤u M[zB + v, i] so that any candidate left-child assignment IL directly equals a row of f , avoiding runtime comparisons with bin boundaries. M Leaf weights: At maximum depth D, a leaf k has weight P P w[k] = − i∈Ik g[i]/( i∈Ik h[i] + α), (3) which is the closed-form minimizer of the second-order objective with L2 regularization [22]. The prediction for sample i is then updated by adding w[k] if i ∈ Ik .
2.2. Cryptographic Primitives
i.e., the canonical gradient and Hessian of logistic loss [22].
2.2.1. Secret Sharing. We adopt (2, 2)-arithmetic additive secret sharing [24]. To share an ℓ-bit integer x ∈ Z2ℓ , party P0 samples r ←$ Z2ℓ , sends r to P1 , and sets ⟨x⟩A0 = x − r, ⟨x⟩A1 = r. Reconstruction is ⟨x⟩A0 + ⟨x⟩A1 mod Z2ℓ . A real x e ∈ R is encoded as x = ⌊x e 2f ⌉ ∈ [−2ℓ−1 , 2ℓ−1 ) using fixed-point representation with precision f . • Addition: ⟨z⟩A = ⟨x⟩A + ⟨y⟩A is computed by Pc locally. • Multiplication: ⟨z⟩A = Fmul (⟨x⟩A , ⟨y⟩A ), where Fmul is a secure two-party protocol using Beaver’s triples [25]. • Division: ⟨z⟩A = Fdiv (⟨x⟩A , ⟨y⟩A ), where Fdiv is a secure two-party protocol using the Goldschmidt method [26]. • Sigmoid: ⟨y⟩A = Fsigmoid (⟨x⟩A ) is a secure two-party protocol for efficiently evaluating the sigmoid function via three-segment Fourier approximation. • ArgMax: ⟨z⟩A = Fargmax (⟨x⟩A ) is a secure two-party protocol to output the shared index z of max x [27]. (2, 2)-boolean sharing [24] is also used. A boolean value x ∈ {0, 1} is XOR-shared as x = ⟨x⟩B0 ⊕ ⟨x⟩B1 : Party P0 samples r ∈ Z2 , sets ⟨x⟩B0 = x ⊕ r, and sends ⟨x⟩B1 = r to P1 . The same generalizes to ℓ-bit strings with r ←$ Z2ℓ . • XOR: ⟨z⟩B = ⟨x⟩B ⊕ ⟨y⟩B is computed by Pc locally. • NOT: ⟨y⟩B = ¬⟨x⟩B , where one party locally computes ¬ on its share, while the other keeps its share unchanged.
Node splitting: Consider a node with index set I. For feature z and threshold ϕ, define the partition IL = {i | X[i, z] ≤ ϕ} and IR = I \ IL . With α ≥ 0 denoting L2
3. For example, consider features age: [<30, ≥30] and weight: [<70kg, ≥70kg], discretized into B = 2 bins. When given n = 4 samples: {(25, 65), (35, 75), (45, 85), (28, 68)}, M = [1010|0101|1010|0101]⊤ .
2.1. Gradient Boosting Decision Tree A GBDT is an ensemble of T decision trees {Tt }Tt=1 that are trained sequentially via gradient boosting [22]. Each tree partitions the feature space at internal nodes and assigns a real-valued weight to each leaf. For input P x, the ensemble T prediction is the sum of leaf weights: ỹ = t=1 Tt (x). Setup and gradient computation: Let D = {(X[i], y[i])}ni=1 be a dataset of n samples with m real-valued features X[i] ∈ Rm and ground-truth label y[i]. We focus on binary classification with logistic crossentropy loss, which is twice differentiable and well suited to second-order boosting [22]. Pt−1 After t−1 trees, for sample i, let ỹ[i] = j=1 Tj (x) and p[i] = sigmoid ỹ[i] . The corresponding first- and secondorder statistics used to fit the t-th tree are respectively g[i] = y[i] − p[i],
h[i] = p[i] · (1 − p[i]),
(1)
• AND: ⟨z⟩B = Fand (⟨x⟩B , ⟨y⟩B ) is achieved by a secure two-party protocol using precomputed boolean triples [24]. • OR: ⟨z⟩B = For (⟨x⟩B , ⟨y⟩B ) via x ∧ y ⊕ (¬x ⊕ ¬y). • Multiplexer: ⟨z⟩A = Fmux (⟨x⟩B , ⟨y⟩A ) takes arithmetic shares ⟨y⟩A and boolean shares of a choice bit ⟨x⟩B as input. It outputs ⟨z⟩A with z = y if x = 1; else z = 0. It can be realized via two FOT calls [19] (introduced below). • Comparison: ⟨z⟩B = Fgreater (⟨x⟩A , ⟨y⟩A ). If x > y , then z is 1; else z is 0. When the bitlength of x and y is small, the secure comparison can be efficiently realized with only FOT [19]. Otherwise, one can recursively divide them as x = x1 ||x2 , y = y1 ||y2 and compares them based on 1{x > y} = 1{x1 > y1 } ⊕ (1{x1 = y1 } ∧ 1{x2 > y2 }), where ∧ and >, = are respectively realized by Fand and FOT [19].
2.2.2. Oblivious Transfer (OT). A 1-out-of-n OT [28] runs between a sender with n messages and a receiver with choice i ∈ [0, n − 1]. The ideal functionality is FOT ; the receiver only learns the i-th message, and the sender learns nothing about i. Ferret OT [29] is used for its low communication. 2.2.3. Circuit-PSI. Private set intersection (PSI) allows two parties to learn X ∩ Y of their input sets while hiding nonintersecting elements. Circuit-PSI [13], [14] further enables evaluating an arbitrary circuit f on payloads attached to items in X ∩ Y , without revealing the intersection itself. Hashing phase: Fix e hash functions h1 , . . . , he . The receiver inserts each x ∈ X into a cuckoo-hash table Tch of (1 + ε)n buckets: first empty among {hi (x)}, with evictions as needed. With suitable (ε, e), no stash is required [13]. The sender inserts each y ∈ Y into all corresponding buckets of a simple-hash table Tsh , permitting multiple items per bucket (vs. at most one in Tch ). Both tables are padded to a common maximum bucket size. Shared hashes ensure any common item lands in one identical bucket on both sides, reducing PSI to per-bucket private set membership (PSM). PSM via OPPRF: An oblivious programmable pseudorandom function functionality FOPPRF realizes PSM [13], [14]. For bucket i, the sender programs PRF Fi such that Fi (y) = ri for every y in Tsh [i] and outputs random values elsewhere. Both parties query FOPPRF on the receiver’s items from Tch ; the receiver obtains ri′ . A secure equality ? test Fequal then yields shared bits of ri = ri′ . Evaluation with payloads: Each item may carry a payload, enabling f to be computed on payloads of the (hidden) intersection [13]. Since a sender’s bucket can contain multiple payloads, two batched OPPRFs select the correct one [13]. Looking ahead, our base design attaches the receiver’s labels and the sender’s (binary-matrix encoded) features as payloads to FCPSI . AnonGBDTOTSA alternates receiver roles and uses OPPRF to synchronize intermediate states; only labels are carried as payloads, improving efficiency. 2.2.4. Additive Homomorphic Encryption (HE). Additive HE supporting homomorphic additions is instantiated from LWE and the ring variant, RLWE [30]. Public parameters
Figure 1. Circuit-PSI asymmetry (cuckoo vs. simple hash): the receiver learns 7 is in the second bucket, but the sender cannot tell which item (4 or 7) is in the second one.
(N, Q) specify the lattice dimension and modulus. Define RQ = ZQ [X]/(X N + 1). Let χsk and χerr denote the secret and error distributions (e.g., {−1, 0, 1}N ). • KeyGen: It generates a key pair (sk, pk) for RLWE (sk ← χsk and pk ∈ R2Q ). Identify the LWE secret key s ∈ ZN Q as the coefficient vector of sk, i.e., s[i] = sk[i], ∀i ∈ [N ]. • Encryption: LWE encryption of m ∈ Z is given as +1 LWEQ,s (m) = (a, b) = (a, ⟨a, s⟩ + e + m) ∈ ZN with Q a ←$ ZN and e ← χ . RLWE encryption of m b ∈ RQ err Q is RLWEQ,sk (m) b = (b a, −b a · sk + eb + m) b ∈ RQ × RQ (or simply JmK b ), where b a ←$ RQ and eb[i] ← χerr . b = RLWEQ,sk (m) • Decryption: An RLWE ciphertext ct b = b bb) = b (b a, b) ∈ RQ × RQ is decrypted by RLWE−1 ( b a , a· Q,sk b sk + b = m b + eb ∈ RQ . (We omit the subscript Q when clear from context.) • PackLWEs: Given a set of LWE ciphertexts {LWEs (mi )}, an FFT-style automorphism-and-keyswitch procedure can pack them into a single RLWE ciphertext [20]. For m(X) b , apply the automorphism EvalAuto(RLWEsk ( m(X)), b t) that b applies X 7→ X t to both ciphertext and key, then perform KeySwitchsk b t 7−→ RLWEsk bt , b t →sk b : RLWEsk bt m b m
b t = sk(X b t ) and m where sk b t = m(X b t ). • Arithmetic share to HE: FA2H . It converts ⟨a⟩A to an RLWE ciphertext JaK. Pl transforms ⟨a[i]⟩Al from Z2ℓ to ZQ , PN −1 then encodes it to the polynomial b al = i=0 ⟨a[i]⟩Al X i . Pc sends RLWEskc (b ac ) to P1−c encrypted under skc . P1−c gets JaK by homomorphically adding b a1−c to RLWEpkc (b a) [5]. • HE to Arithmetic share: FH2A . It converts RLWE JaK encrypted by Pc to ⟨a⟩Al . P1−c samples a random rb ←$ RQ , b by homomorphically subtracting it from JaK. Pc and gets ct b and sets its coefficient vector as ⟨a⟩Ac . P1−c sets decrypts ct A ⟨a[i]⟩1−c by transforming rb[i] from Q to Z2ℓ [5].
3. System and Security Models Two parties P0 and P1 hold vertically partitioned data (IDl , Xl ) for l ∈ {0, 1}, where IDl draws from a common identifier domain. Identifier lists may overlap, while feature spaces are disjoint: Xl ∈ Rnl ×ml with distinct column sets. For simplicity, we assume m0 = m1 = m and n0 = n1 = n
Π Functionality FGBDT (InputΠ 0 , Input1 , pp) Π InputΠ 0 = {ID0 , X0 , y}, Input1 = {ID0 , X1 } Π A Output0 = {C0 , {⟨w[k]⟩0 }k≥2D−1 }, where (k) (k) (k) C0 [k] = (z∗ , u∗ ) if z∗ < m; otherwise, C0 [k] =⊥ Π Output1 = {C1 , {⟨w[k]⟩A1 }k≥2D−1 }, where (k) (k) (k) C1 [k] = (z∗ , u∗ ) if z∗ ≥ m; otherwise, C1 [k] =⊥
Figure 2. Ideal private GBDT training functionality: Outputs reveal only per-party best splits C and secret-shared weights ⟨w⟩A .
(unbalanced n0 ̸= n1 are considered in experiments). Let IDl [i] be the i-th identifier of Pl and Xl [i] its associated feature vector. The parties run a two-party protocol Π to train a GBDT on the (implicit) join of their datasets. All prior work [5], [7], [8] assumes pre-aligned data, i.e., X0 [i] and X1 [i] refer to the same sample. This implicitly discloses ID0 ∩ ID1 , (in the worst case, all identifiers), enabling re-identification. In contrast, our designs reveal no identifiers, no membership in the intersection, not even the cardinality |ID0 ∩ ID1 | nor whether the intersection equals the entire dataset; it also hides all alignment information (e.g., for a common item at ID0 [i], the counterparty’s index j such that ID0 [i] = ID1 [j] is never learned). Figure 2 specifies the ideal functionality FGBDT for one tree in T with two parties’ data and public parameters pp. Without loss of generality, P0 supplies labels y. Each tree is complete and balanced with depth D; internal nodes are indexed by 1 ≤ k < 2D−1 and leaves by 2D−1 ≤ k < 2D . Internal computation is done on the implicit join ID0 ∩ID1 : Gradients/Hessians are computed with sigmoid approximation and then aggregated as histograms per bin (Section 2.1). For each internal node k and candidate (z, u), the split gain (k) (k) Lsp is evaluated as in Eq. (2); the best split (z∗ , u∗ ) (k) maximizing Lsp is revealed to Pl owning z∗ . Given the split, sample indicators update via exclusive-prefix matrices. Upon completion, Pl receives its own best splits Cl [k] for k < 2D−1 , and the leaf weights are additively secret-shared. We consider static and semi-honest probabilistic polynomial time (PPT) adversaries [5], [7], [8], which follow the protocol without deviation but try to learn more beyond the outputs. Formally, let Π be a two-party protocol computing a deterministic functionality F : {0, 1}∗ × {0, 1}∗ 7→ {0, 1}∗ ×{0, 1}∗ . The output of F is a pair, F0 (x0 , x1 ) to P0 and F1 (x0 , x1 ) to P1 . For i ∈ {0, 1}, the view of Pi during an execution of Π on (x0 , x1 ) is denoted by ViΠ (x0 , x1 ). Definition 3.1. For a function F , Π privately computes F if there are PPT algorithms S0 and S1 such that, i ∈ {0, 1}, Si (xi , Fi (x0 , x1 )) ≈c ViΠ (x0 , x1 ), ∀x0 , x1 ∈ {0, 1}∗ ,
where ≈c denotes computational indistinguishability. Theorem 3.1 (Modular Composition [31]). Let F1 , . . . , Fm be ideal two-party functionalities, and let Π be a two-party protocol in the hybrid model that can invoke at most one of F1 , . . . , Fm per round. For i ∈ [m], let fi be a real
two-party protocol that realizes Fi in the computational setting. Then, for any PPT passive adversary A and any PPT environment Z , there exists a PPT passive simulator F1 ,F2 ,...,Fm S such that SimΠ,S,Z ≈c ExecΠ (f1 ,f2 ,...,fm ) ,A,Z .
4. AnonGBDT: Base Design Squirrel [5], a recent two-party secure GBDT protocol, presumes a priori alignment: X0 [i] and X1 [i] are the same sample i, enabling direct training on X0 ∥ X1 . In practice, independently maintained data only partially overlap; perfect alignment is uncommon, rendering Squirrel impractical without a preceding private-matching step. Circuit-PSI is utilized to reconcile ID0 and ID1 before training, without revealing identifiers. Subsequent training then follows Squirrel’s workflow (using primitives in Section 2.2), with targeted adaptations to accommodate circuitPSI’s asymmetric hashing and payload interface. A brief recap of Squirrel is first given, preceding our base design. We follow their convention of underlining, e.g., sk denotes a secret key under the lifted HE parameters such as N .
4.1. Revisit of Squirrel Data pre-processing: Each party Pl discretizes raw features Xl into a one-hot bin-indicator matrix Ml and its exclusivef l , as detailed in Section 2.1. prefix variant M Private sample tracking: At each node k , an n-bit indicator b(k) (initialized to 1n at the root) is maintained, where b(k) [i] = 1 iff sample i reaches node k . To keep b(k) private, (k) (k) Squirrel uses “AND-style” sharing4 : b(k) = b0 ∧ b1 . If party Pc 5 owns the best split (z∗ , u∗ ), it locally forms (k) f c [z∗ B+u∗ ] and updates the (plaintext) assignment b∗ = M (k)
b(2k) = b(k) c c ∧ b∗ ,
(2k) b(2k+1) = b(k) , c c ⊕ bc
(4)
(k)
while P1−c copies its share without b∗ . This AND-sharing update is incompatible with XOR shares produced after circuit-PSI alignment; Section 4.2.2 introduces an oblivious indicator synchronization (OIS) for XOR-shared b(k) . Gradient computation: Fourier-series sigmoid [32] and other nonlinear functions [33] have been studied for efficient and accurate secure computation. To obtain arithmetic shares ⟨g⟩Al and ⟨h⟩Al (Eq. (1)), Squirrel adopts a Fourierseries sigmoid approximation that reduces secure multiplications (hence communication) compared to spline-based methods [7], [34], yet still contributes ≈50% of total traffic. x ∈ [−µ, µ], it evaluates a0 + PJSpecifically, for L+1 , with µ = 5.6, degree J = 8, j=1 aj sin 2πjx/2 scaling factor L = ⌈log2 µ⌉, and maximal error 0.022; outside this range, outputs are clipped to 0 (for x < −µ) or 1 (for x > µ). This requires only secure comparisons with ±µ and secure multiplications for the series. Section 4.2.3 4. This sharing cannot “perfectly” hide b(k) : If a party’s share equals 0, it immediately learns the corresponding secret bit is 0. 5. Pc : asymmetric steps; only Pc acts. Pl : symmetric steps; both act.
optimizes such an approximation by lowering J and reusing primitives in ±µ comparisons. Gradient aggregation: We describe the processing for g (it applies identically to h). Non-reachable samples are filtered by g(k) = b(k) ⊙g, where ⊙ is element-wise multiplication, realized via a secure multiplexer: ⟨g(k) ⟩Al = Fmux (⟨b(k) ⟩Bl , ⟨g⟩Al ).
Functionality FOIS f 1 ⟩B , ⟨b⟩B , M f 0 , and {(z∗ , u∗ ) / ⊥} P0 ’s Input: ⟨M 0 0 B B f P1 ’s Input: ⟨M1 ⟩1 , ⟨b⟩1 , and {⊥ /(z∗ , u∗ )} Output: ⟨bL ⟩Bl and ⟨bR ⟩Bl for ‘L’eft and ‘R’ight children. Protocol ΠOIS
(5)
For the left child 2k , Squirrel halves the usage of OT based (k) (k) on g(2k) = b(2k) ⊙g = (b(k) ∧b∗ )⊙g = b∗ ⊙g(k) given (k) non-shared b∗ (vs. simply using Fmux over AND-shared b(2k) ). The right child is g(2k+1) = g(k) − g(2k) . Filtered P gradients are then binned by pick-then-sum: e(k,c) [j] = i|Mc [j,i]=1 g(k) [i] (for i ∈ [n], j ∈ [1, mB]), g or equivalently Mc · g(k) , which is realized by the secure binary-matrix-vector multiplication FBinMatVec : i) convert ⟨g(k) ⟩Al to RLWE-encrypted Jg(k) K by FA2H , ii) achieve efficient homomorphic aggregation on extracted e(k) K within the LWE ciphertext from Jg(k) K, and pack to Jg RLWE domain via PackLWEs. which we optimize; e(k) K back to shares ⟨g e(k) ⟩Al via FH2A . iii) convert Jg In our anonymous setting, the circuit-PSI sender does not know the correspondence between M[:, i] and g(k) [i], making FBinMatVec inapplicable as is; Section 4.2.1 addresses this by treating M as an additional payload. Best-split selection: For each candidate (z, u), the split gain Lsp (Eq. (2)) is securely evaluated using Fdiv and Fmul . Fargmax reveals the maximizer (z∗ , u∗ ) to its owner.
4.2. Our Base Design We begin with the stash-less circuit-PSI [15], using P0 as receiver and P1 as sender, to privately reconcile ID0 and ID1 . The output is XOR-shared b(1) ∈ {0, 1}(1+ε)n over the receiver’s cuckoo-hash order (Section 2.2.3), replacing the 1n root indicator in Squirrel. Subsequent training avoids leaky AND-sharing by maintaining XOR shares. Encoding the entire training pipeline as one circuit with f 0 , y) and (M1 , M f 1 ) is impractical. We payloads (M0 , M minimize payloads and exploit circuit-PSI’s order alignment to enable efficient, order-dependent steps. 4.2.1. Gradient Histogram Aggregation. Order after circuit-PSI aligns elements for the receiver: the cuckoo-hash permutation fixes a one-to-one correspondence between the intersection positions and local samples. Concretely: Receiver side P0 . As M0 is aligned (in cuckoo order) with samples’ gradient shares from Fsigmoid and Fmul (Line 4, Figure 4), P0 can build histograms with the communicationfriendly FBinMatVec as in Squirrel; only y is payload. Sender side P1 . The sender’s simple hashing creates a oneto-many mapping, so it does not learn which gradient index matches which column of M1 . To restore compatibility, M1 is carried as a circuit-PSI payload, yielding XOR-shared
(1+ϵ)n 1: P0 : draw a random mask ⟨b∗ ⟩B . 0 := r ←$ {0, 1} 2: if P0 owns (z∗ , u∗ ) then
f 0 [z∗ B + u∗ ]. 3: P0 : set b∗ = M 4: P0 : share ⟨b∗ ⟩B1 = b∗ ⊕ r with P1 . 5: else 6: for i ∈ [(1 + ϵ) · n] do f 1 ⟩B [j, i], ∀j ∈ [m · B]. P0 : e r[j] = r[i] ⊕ ⟨M 0 P0 (as OT sender): run FOT (e r). P1 (as OT receiver): r′ [i] ← FOT (z∗ B + u∗ ) f 1 ⟩B [z∗ B + u∗ , i]. 10: P1 : ⟨b∗ [i]⟩B1 = r′ [i] ⊕ ⟨M 1 B B 11: Pl computes ⟨bL ⟩B l = Fand (⟨b∗ ⟩l , ⟨b⟩l ) and R B L B B ⟨b ⟩l = ⟨b ⟩l ⊕ ⟨b⟩l . ▷ Secure evaluation of Eq. (4) 7: 8: 9:
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: P ∀(z, u) : i Fmux ⟨M1 [zB + u, i]⟩Bl , ⟨g[i]⟩Al , (6) and likewise for h. This avoids generic secure matrix multiplication (which would invoke Fmul per entry) while using aligned order: ⟨M1 [·, i]⟩Bl , ⟨g[i]⟩Al refer to the same sample. Root filtering uses b(1) : both parties compute ⟨g(1) ⟩Al = Fmux (⟨b(1) ⟩Bl , ⟨g⟩Al ) and similarly for h (Line 5, Figure 4). Complexity: For M0 , O(Bmn) invocations of Fmux , each using two FOT calls (that send O(ℓ) bits per OT); the total communication round is O(1). For M1 , FBinMatVec incurs O(n log Q) bits via FA2H and O(2Bm log Q) bits via FH2A ; the communication uses two rounds. 4.2.2. Oblivious Indicator Synchronization. Sample indicators are updated from the chosen split via the exclusivef . As a circuit-PSI receiver, P0 knows which prefix matrix M f column of M0 6 matches the correct indicator index. The f 1 as a payload. sender P1 does not; it needs to carry M f Because both M1 and indicators b(k) are XOR-shared, the plaintext (local) update Eq. (4) is inapplicable. To this end, we introduce an OT-based oblivious indicator synchronization (OIS) protocol, whose functionality FOIS appears in Figure 3: If P0 owns (z∗ , u∗ ), it secret-shares f 0 [z∗ B + u∗ ] with P1 (Lines 1–4). Otherwise, P0 b∗ = M f 1 and, for each row, (as OT sender) masks its share of M the two parties execute a 1-out-of-mB OT such that P1 (as OT receiver) obtains correct ⟨b∗ ⟩B1 given its private choice (z∗ , u∗ ). In either case, the left-child indicator is then computed with secure AND Fand , and the right-child indicator by bitwise XOR (Section 4.1). 6. It is resized to mB × (1 + ε)n after circuit-PSI cuckoo hashing.
Π Base Base AnonGBDT ΠGBDT (InputΠ 0 , Input1 , pp)
P0 ’s Input: Identifier lists ID0 , raw feature matrix X0 , and labels y (Initially, ỹ = 0). P1 ’s Input: Identifier lists ID1 and raw feature matrix X1 , and sk1 for FA2H , sk1 for FH2A . Public parameters: pp = {T, D, B}, and lifting key LKsk1 →sk1 for KeySwitch. Π Output: OutputΠ 0 for P0 and Output1 for P1 . m·B×n fl. 1: Pl discretizes Xl to Ml ∈ {0, 1} , which is aggregated to M ▷ Data pre-processing as in Squirrel (1) B A B f B f 1 ). 2: Pl : ⟨b ⟩l , ⟨y⟩l , ⟨M1 ⟩l , ⟨M1 ⟩l ← FCPSI (ID0 ; ID1 ), with P0 ’s payload y and P1 ’s payloads (M1 , M 3: for tree t ∈ Tt do 4: Pl computes gradients ⟨g⟩Al , ⟨h⟩Al using Fsigmoid (⟨ỹ⟩Al ) and Fmul based on Eq. (1). ▷ Per-sample gradient 5: Pl filters gradients ⟨g(1) ⟩Al , ⟨h(1) ⟩Al at the root using Fmux given ⟨b(1) ⟩Bl based on Eq. (5). 6: for internal nodes k ∈ {1, 2, . . . , 2D−1 − 1} do 7: if k is 1 or even then ▷ Per-bin gradient 8: Pl aggregates gradients over M0 (as in Squirrel): e (k,0) ⟩A = FBinMatVec ({⟨g(k) ⟩A ||⟨h(k) ⟩A , M0 }, {⟨g(k) ⟩A ||⟨h(k) ⟩A , sk1 }). e(k,0) ⟩Al ||⟨h ⟨g 0 0 1 1 l 9:
10: 11: 12: 13: 14: 15: 16: 17: 18: 19:
Pl aggregates gradients over ⟨M1 ⟩Bl using our Fmux -based approach (see Eq. (6)): e (k,1) [j]⟩A ) = P Fmux (⟨M1 [j, i]⟩B , ⟨g(k) [i]⟩A (/⟨h(k) [i]⟩A )) . e(k,1) [j]⟩Al (/⟨h ∀j ∈ [mB] : ⟨g l l l l i e (k) ⟩A = ⟨h e (k,0) ⟩A ∥⟨h e (k,1) ⟩A . e(k) ⟩Al = ⟨g e(k,0) ⟩Al ∥⟨g e(k,1) ⟩Al , ⟨h Pl locally concatenates the shares as ⟨g l l l (k) A (k/2) A (k−1) A e (k) A (k/2) A (k−1) A e e e ⟩l = ⟨g e e else Pl gets ⟨g ⟩l − ⟨g ⟩l , ⟨h ⟩l = ⟨h ⟩l − ⟨h ⟩l (as in Squirrel). (k) Pl computes the splitting scores ⟨Lsp ⟩Al using Fmul and Fdiv for all (z, u) based on Eq. (2). (k) A (k) A (k) Pl gets ⟨z∗ ⟩l , ⟨u∗ ⟩l ← Fargmax (⟨Lsp ⟩Al ). ▷ Best split selection (k) (k) (k) Open a bit c ← Fgreater (⟨z∗ ⟩Al , m − 1) and reveal (z∗ , u∗ ) to Pc , who writes it to OutputΠ c . f 1 ⟩B , ⟨b(k) ⟩B , M f 0 }; {⟨M f 1 ⟩B , ⟨b(k) ⟩B }) with Pc ’s (z∗(k) , u(k) Pl updates ⟨b(2k) ⟩Bl , ⟨b(2k+1) ⟩Bl ← FOIS ({⟨M ∗ ) 0 0 1 1 Pl updates left-child gradients: ⟨g(2k) ⟩Al = Fmux (⟨b(2k) ⟩Bl , ⟨g(k) ⟩Al ), ⟨h(2k) ⟩Al = Fmux (⟨b(2k) ⟩Bl , ⟨h(k) ⟩Al ). Pl updates right-child gradients: ⟨g(2k+1) ⟩Al = ⟨g(k) ⟩Al − ⟨g(2k) ⟩Al , ⟨h(2k+1) ⟩Al = ⟨h(k) ⟩Al − ⟨h(2k) ⟩Al . Pl computes leaf weights ⟨w⟩Al using Fdiv based on Eq. (3) and writes them in OutputΠ l . Pl updates ⟨ỹ[i]⟩Al by accumulating the result of Fmux (⟨b(k) [i]⟩Bl , ⟨w[k]⟩Al ) (∀i) over all leaves k . 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 Sigmoid Approximation. We replace the integral-derived Fourier coefficients with least-squares fitting to estimate aj∈[0,J] , allowing us to reduce the order to J = 3 while achieving better accuracy and efficiency. We retain µ = 5.6 and evaluate only with Fmul , using an implementation optimized for trigonometric inputs within [−1, 1]; see Appendix A.1. The resulting average/maximum errors are 0.002/0.015 (vs. 0.022 in Squirrel); see Appendix A.2. We also streamline secure comparisons with ±µ. Under fixed-point representation with precision 2f , the two thresholds share their f − δ least-significant bits; hence, within Fgreater , we reuse FOT and Fand on the shared bits. Overall, our new sigmoid costs 33% of runtime and 16% of communication of the Squirrel variant. Figure 4 presents the base AnonGBDT workflow, with differences from Squirrel highlighted in blue. Two substitutions enable anonymous training under circuit-PSI alignment: i) gradient-histogram aggregation at the sender via Fmux over payload-shared M1 (Section 4.2.1); ii) indicator
synchronization via FOIS (Section 4.2.2), ensuring XORshared indicators remain aligned and usable by both parties.
5. AnonGBDT: OT-light, Symmetric Alignment The base design conceals intersection membership, cardinality, and alignment information throughout training, offering stronger privacy than prior work [5], [7], [8]. Its communication remains substantial: i) histogram construction via Fmux requires O(mnB) many 1-out-of-2 OTs, and ii) FOIS runs one 1-out-of-mB per row over (1 + ε)n rows (with ε the cuckoo-hash parameter). The histogram term dominates. We eliminate it via a dual-circuit-PSI framework.
5.1. Our Dual-circuit-PSI Framework Circuit-PSI is asymmetric: only the receiver learns the (bucketed) input-output correspondence. We “symmetrize” this by running two circuit-PSI instances in parallel with swapped roles, so each party is a receiver once and learns the correspondence for exactly one instance. This allows both parties to keep M0 and M1 locally (no payload for M1 ), and to aggregate gradients on non-shared matrices solely with FBinMatVec (as in Squirrel), removing the many calls to Fmux . We further accelerate FBinMatVec
by replacing its subroutines, PackLWEs-then-LWEDimLift, with our FastPackLWEs (see Section 5.2). Figure 5 overviews the dual-circuit-PSI. Superscripts (k, 0) and (k, 1) respectively denote the first and second instances at node k . In instance 0, P0 (receiver) inputs ID0 with payload y, yielding ⟨b(1,0) ⟩B and ⟨y0 ⟩A . Roles are reversed in instance 1, producing ⟨b(1,1) ⟩B and ⟨y1 ⟩A . Each instance applies its own cuckoo permutation, so order-dependent steps must be done per instance, e.g., gradient computation uses both ⟨y0 ⟩A and ⟨y1 ⟩A , whereas (orderindependent) aggregation runs once locally over M0 or M1 . Base OIS limitation: With dual-circuit-PSI, updating the two XOR-shared indicators b(k,0) and b(k,1) is non-trivial. If the split owner Pc is the receiver for an instance, it can update as in base OIS (Lines 1–4 and 11, Figure 3). If it is the sender for the other instance, it lacks the share f 1−c (no longer a payload of P1−c ), so base OIS of M (Lines 6–11) fails. We resolve this with a new OPPRF-based OIS (Section 5.3), which supports level-wise batching for efficiency. With these changes and engineering optimizations (Section 5.4), AnonGBDTOTSA significantly reduces runtime and communication versus the base one (Section 6).
5.2. Faster LWE Ciphertext Packing The secure matrix-vector multiplication FBinMatVec uses RLWE encryption for computational efficiency and outputs n LWE ciphertexts, which incur large communication because FH2A must convert these LWE ciphertextsto shares. Communication can be cut by packing several LWE ciphertexts with a smaller dimension (N ) into a single RLWE ciphertext with a larger dimension (N ). Squirrel does so in two stages: LWEDimLift (lift dimension N → N ) followed by PackLWEs (recursive merging). We replace this flow with FastPackLWEs followed by PackRLWEs (Algorithms 1 and 2). Figure 7 shows the adapted version. We also modify FBinMatVec from Squirrel with changes boxed (Line 6). Let {LWEs (mi )}0≤i<n , n = 2τ , be encrypted under secret s (the vector representation of FA2H ’s sk). For each adjacent pair LWEs (m2j ) = (a1 , b1 ), LWEs (m2j+1 ) = (a2 , b2 ), we can manipulate them as a new RLWE ciphertext pair: b a=b a1 + b a2 · X N/2 , bb = b1 + b2 · X N/2 , (7) PN −1 under a new secret sb = sk[0] − k=1 sk[k] · X N −k , where PN −1 b ai = k=0 ai [k] · X k (i ∈ {1, 2}). The 0- and (N/2)-th coefficients, when decrypting (b a, bb) by sb, are exactly m2j and m2j+1 , i.e., the two messages are packed within one RLWE ciphertext without lifting their dimensions individually. As sb is insecure (half its coefficients are zero), we immediately switch it to a valid RLWE secret key sk with one KeySwitch call (in Line 3). By merging all adjacent ones, we thus obtain n/2 RLWE ciphertexts. To integrate this idea, we remove the first recursion of PackLWEs, leading to PackRLWEs (Algorithm 2). Also, at Line 5, we change t from N/2τ to N/2τ +1 .
Algorithm 1 FastPackLWEs (Fast LWE Packing) Input: LWE ciphertexts {LWEs (mi )}0≤i<n (for n = 2τ < N ) and lifting key LKsk→sk . b. Output: An RLWE ciphertext ct 1: for i ∈ [0, n) with step-size as 2 do c∗ j = (b aj , bbj ), where 2: Build an RLWE ciphertext ct j = i/2 and b aj , bbj are given as Eq. (7). b j = KeySwitchsk→sk (ct c∗ j ) based on LKsk→sk . 3: ct b ← PackRLWEs({ct b j }). 4: return ct Algorithm 2 PackRLWEs (RLWE Ciphertext Packing) b j } for some j ∈ [2τ ]. Input: RLWE ciphertexts {ct b. Output: An RLWE ciphertext ct 1: if τ = 0 then b ← ct b 0. 2: return ct b b 2j |j ∈ [0, 2τ −1 − 1]}). 3: cteven ← PackRLWEs({ct b odd ← PackRLWEs({ct b 2j+1 |j ∈ [0, 2τ −1 − 1]}). 4: ct b ← (ct b even +X t · ct b odd )+EvalAuto(ct b even − 5: return ct b odd , N + t), where t = N/2τ +1 . X t · ct Complexity: FastPackLWEs processes n/2 pairs, cutting the cost of LWEDimLift [5] in half. PackRLWEs now requires only τ − 1 recursions, again halving the workload compared with PackLWEs [5]. Consequently, the overall ciphertext-packing time of FBinMatVec is reduced by 50%.
5.3. OPPRF-based OIS The dual framework is symmetric across parties, but each instance remains asymmetric. Assume Pc owns the best split (z∗ , u∗ ). Figure 8 shows our new OPPRF-based OIS (c) f c [z∗ B + (OOIS). If Pc is the receiver, it sets b∗ = M u∗ ] secret-shares it with P1−c , from which the children’s ⟨b(L,c) ⟩Bl , ⟨b(R,c) ⟩Bl are derived (Lines 1–4) as in base OIS. If Pc is the sender, synchronizing the children’s indicator (c) shares given b∗ is tricky. Recall that circuit-PSI facilitates the inclusion of payloads through two batch OPPRFs. The first identifies intersecting items via PSM testing. The second distinguishes sender-side payloads of items within each bucket and selects the “correct” one for computation: If Tch [i] is j -th item in Tsh [i], then the programmed OPPRF output at the receiver is a share of Tsh [i, j]’s payload. The remaining OOIS steps (Lines 5–10) build atop this (c) concept: Firstly, Pc reorders b∗ from its cuckoo-hash order to the raw order in IDc , producing a temporary indicator b′∗ for the other instance. It then samples a random vector r1−c and forms XOR share of b′∗ . Each sample IDc [i′ ] resides in some bucket T1−c sh [i, j] under the other instance’s e simple hashes. This lets Pc build a key-value table T with those items as keys and the corresponding shares of (1−c) b∗ as values (derived from b′∗ and r1−c ). A single call to FOPPRF supplies P1−c with the complementary shares of (1−c) b∗ . Finally, both parties obtain the left- and right-child indicators via Fand and string XOR as in Line 4.
Figure 5. Overview of AnonGBDTOTSA (with our key contributions highlighted in red)
Functionality FBinMatVec Pc ’s Input: gradients share ⟨g⟩Bc , binary feature representation Mc ∈ {0, 1}B P1−c ’s Input: gradients share ⟨g⟩A1−c , RLWE sk1−c for FA2H , and sk1−c for FH2A Public parameters: KeySwitch lifting key LK Output: ⟨Mc · g⟩Al to Pl .
Protocol ΠBinMatVec 1: Jointly run FA2H , P1−c inputs ⟨g⟩A 1−c , sk 1−c , and Pc 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). Senderchosen values are returned on a sparse set of indices and pseudorandom fillers appear elsewhere. We keep the OPPRF interface because our pipeline already uses batch OPPRF at two call sites. This preserves batching in FBOIS . Level batching: All internal nodes share IDc (as the hash table’s key set), so we pack all node indicators per level into one OPPRF value. The batched variant (BOIS, Figure 12 in Appendix B) reduces the O(2D ) cost to O(D) for depth D. Complexity: For a batch of nodes, it first calls one FOPPRF , costs O(nℓ) bits with O(1) rounds. Then, it calls 2n Fand (each sends O(ℓ) bits) with O(1) rounds. Theorem 5.1. ΠBOIS realizing FBOIS in Figure 12 is a secure protocol under FOPPRF and Fand hybrids. We defer the proof to Appendix D due to space limits.
inputs ⟨g⟩Bc ; Pc gets JgK, and P1−c gets nothing.
2: Pc initializes a size-(B · m) array of LWE encryption
of 0, denoted by ct[j] for j ∈ [B · m]. 3: for all position (j, i) such that M[j, i] = 1 do ¯ i] from JgK that decrypts 4: Pc extracts LWE ct[j,
to g[i] under P1−c ’s secret key. ¯ i] Pc : ct[j] = ct[j] + ct[j, ▷ pick-then-sum 6: Pc : JMc · gK ← FastPackLWEs({ct[j]}j∈[m·B) , LK) 7: Jointly invoke FH2A , Pc inputs JMc · gK while P1−c inputs sk1−c . Both parties return the resulting arithmetic share ⟨Mc · g⟩A . 5:
Figure 7. Functionality and protocol of BinMatVec
5.4. Further Optimizations • High-precision score computation: With fixed-point precision 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 the same sample indicator b(k) (Eq. (5)). Real values (e.g., every entry of g) are encoded as ℓ-bit integers by fixed-point representation. As the security parameter is λ = 2ℓ = 128, we can halve
Functionality FOOIS f c , ⟨b(0) ⟩Bc , ⟨b(1) ⟩Bc , (z∗ , u∗ ), and Pc ’s Input: M simple hash table T1−c sh . P1−c ’s Input: ⟨b(0) ⟩B1−c , ⟨b(1) ⟩B1−c , and cuckoo hash table T1−c ch . Output: ⟨b(L,0) ⟩B , ⟨b(R,0) ⟩B , ⟨b(L,1) ⟩B , ⟨b(R,1) ⟩B for the ‘L’eft and ‘R’ight children of the two instances Protocol ΠOOIS c (1+ϵ)n 1: Pc gets a random mask ⟨b∗ ⟩B . c := r ←$ {0, 1} (c)
2: Pc sets b∗
f c [z∗ B + u∗ ]. =M (c) B (c) 3: Pc shares ⟨b∗ ⟩1−c ← b∗ ⊕ rc with P1−c . (c) B (c) B 4: Pl derives ⟨b(L,c) ⟩B l = Fand (⟨b∗ ⟩l , ⟨b ⟩l ) (R,c) B (L,c) B and ⟨b ⟩l = ⟨b ⟩l ⊕ ⟨b(c) ⟩Bl . (c) 5: Pc “reorders” b∗ to b′∗ to align with IDc . (1−c) B 6: Pc samples ⟨b∗ ⟩c = r1−c ←$ {0, 1}(1+ϵ)n . 7: ∀j ∈ [0, e), ∀i ∈ [0, (1 + ϵ)n): B 1−c Pc creates a table T = {(T1−c sh [i, j], ⟨b∗ [i]⟩1−c }, (1−c) B ′ ′ 1−c where ⟨b∗ [i]⟩1−c = b∗ [i ] ⊕ r [i] and IDc [i′ ] is placed in T1−c sh [i, j] via simple hashing. (1−c) B 8: ⟨b∗ ⟩1−c ← FOPPRF ({T}, {T1−c ch }). (1−c) B (L,1−c) B 9: Pl runs ⟨b ⟩l = Fand (⟨b∗ ⟩l , ⟨b(1−c) ⟩Bl ). (R,1−c) B (L,1−c) B 10: Pl runs ⟨b ⟩l = ⟨b ⟩l ⊕ ⟨b(1−c) ⟩Bl . 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., PN /2−1 PN −1 b al = ⟨g[i]⟩Al X i + i=N /2 ⟨h[i]⟩Al X i (see Seci=0 tion 2.2). After pick-then-sum, two LWE ciphertexts (of dimension N ) can be directly packed in one RLWE ciphertext (of dimension N ) without KeySwitch, thereby reducing one recursion of FastPackLWEs. • Skipping FA2H for the split owner: If party Pc holds the best split at node k , it locally allocates the RLWE-encrypted g(k,c) and h(k,c) to bins at node 2k and aggregates them, eliminating the costly share-to-ciphertext conversion. • Dummy-free aggregation: In FBinMatVec , ciphertexts follow the cuckoo-hash order, including the εn dummies. By realigning Ml and the ciphertext list with the original row order of Xl , each party sums only genuine samples, avoiding dummy-related overhead. • Lightweight oblivious argmax: Pairwise comparisons use OTs, outperforming GC variants [19]. Because the splitindex space is public, the final selection is obtained directly with FOT , removing the extra Fmux step of Squirrel [5]. • Erasing superfluous coefficients in FastPackLWEs: To prevent leakage, the prior work [20] zeroizes useless coefτ τ ficients between X i∗N/2 and X (i+1)∗N/2 for i ∈ [2τ − 1] by the trace function, which recursively evaluates EvalAuto on the ciphertexts after PackLWEs. Instead, we just add
TABLE 2. C OMMUNICATION C OMPLEXITY AND ROUNDS OF EACH COMPONENT OF AnonGBDT (BASE VERSUS F INAL )
Component Dual-circuit-PSI GHA (Base) GHA (Final) FOIS (Base) FBOIS (Final)
Complexity
Round
O(nℓ) O(2Bmnℓ + n log Q +2Bm log Q) O(2n log Q + 4Bm log Q) O(Bmnℓ) per node O(3nℓ) per level
O(log ℓ) + 1 O(1) 2 O(1) O(1)
randomness to nullify these coefficients (without EvalAuto but sharing a similar purpose) to improve efficiency.
5.5. Bringing Everything Together Figure 9 presents AnonGBDTOTSA . Two circuit-PSI instances run in parallel with swapped roles. For instance i ∈ {0, 1}, inputs are ID0 and ID1 , and the only payload is y, producing the root indicator shares ⟨b(1,i) ⟩Bl and label f i stay local. shares ⟨yi ⟩Al . Unlike our base scheme, Mi , M For each tree, both parties derive and filter ⟨g(1,i) ⟩Al and ⟨h(1,i) ⟩Al per instance (Lines 6–7). Nodes are processed level-wise using BOIS (Figure 12). At depth d, two public sets k0 , k1 record the owner of each node’s best split. Histogram construction: For roots and left children, both parties aggregate gradients with FBinMatVec over M0 and M1 (accelerated by FastPackLWEs) and then concatenate locally. For right children, histograms are obtained by subtracting the parent and left-child values. Aggregation is order-independent, so it runs only once (not per instance). Split selection: Split gains for all candidates are evaluated (k) (k) with Fmul and Fdiv (Line 16. Fargmax reveals (z∗ , u∗ ) to its owner Pc , which adds k to kc . Given k0 , k1 , FBOIS updates level-wise indicators for the next level’s filtering. Leaf weights: For each leaf k , the weight is derived from whichever gradient share ⟨g(k,i) ⟩Al has fewer samples (for order independence), and the predictions are accumulated. Confining heavy computation to local data removes the OT-intensive histogram phase of the base design. The tradeoff is maintaining one “logical” tree per instance, increasing total communication to at most 2(1 + ε)× that of Squirrel. 5.5.1. Complexity. Table 2 reports the per-component complexity for AnonGBDT. AnonGBDTOTSA achieves its performance gains primarily due to: i) In base gradient histogram aggregation (GHA), the dominant cost is Fmux with complexity O(Bmnl), which is eliminated in AnonGBDTOTSA , and ii) Unlike the base FOIS , which is invoked per node and scales linearly with Bm, its batch extension FBOIS is invoked per level. OTSA Theorem 5.2. ΠGBDT (Figure 9) is anonymous GBDT training under Fargmax , FBOIS , FBinMatVec (with FA2H , FH2A ), FCPSI , Fdiv , Fgreater , Fmul , Fmux , Fsigmoid -hybrid and semantically-secure RLWE encryption.
We defer the proof to Appendix D due to space limits.
Π0 OTSA 0 AnonGBDT ΠGBDT (InputΠ 0 , Input1 , pp)
P0 ’s Input: ID0 , feature X0 and label y. P1 ’s Input: ID1 , feature X1 . Public parameters: pp = {D, B, T, (sk l , pk l ) for FA2H , (skl , pkl ) for FH2A , KeySwitch Lifting Key LKskl →skl }. Π Output: OutputΠ 0 for P0 and Output1 for P1 fl. 1: Pl discretizes its raw data Xl to Ml ∈ {0, 1}m·B×n , which is aggregated to M (1,0) B 0 A 0 0 2: For instance i = 0: ⟨b ⟩l , ⟨y ⟩l ← FCPSI ({ID0 y}; {ID1 }), with P0 ’s Tch and P1 ’s T0sh . (1,1) B 1 3: For instance i = 1: ⟨b ⟩l , ⟨y1 ⟩Al ← FCPSI ({ID1 }; {ID0 , y}), with P1 ’s T1ch and P0 ’s T1sh . 4: for tree t ∈ Tt do 5: For i ∈ {0, 1}: Pl derives gradients ⟨g(1,i) ⟩Al , ⟨h(1,i) ⟩Al at root using Fsigmoid (⟨ỹi ⟩Al ) and Fmul ; see Eq. (1). 6: For i ∈ {0, 1}: Pl filters ⟨g(1,i) ⟩Al , ⟨h(1,i) ⟩Al at root using Fmux given ⟨b(1,i) ⟩Bl ; see Eq. (5). 7: for level d ∈ {1, 2, . . . , D − 1} of the tree do 8: Both parties maintain two public sets k0 ← ∅, k1 ← ∅. ▷ Record node k ’s best split is at P0 or P1 9: for the internal nodes k ∈ {2d−1 , . . . , 2d − 1} at level d do ▷ Batch updates on level d for BOIS 10: if k is 1 or even then 11: Pl aggregates gradients over M0 (as in Squirrel) with our new subroutine FastPackLWEs: e (k,0) ⟩A = FBinMatVec ({⟨g(k,0) ⟩A ||⟨h(k,0) ⟩A , M0 }, {⟨g(k,0) ⟩A ||⟨h(k,0) ⟩A , sk1 }). e(k,0) ⟩Al ||⟨h ⟨g 0 0 1 1 l 12: Similarly, Pl runs FBinMatVec with FastPackLWEs over M1 to get ⟨g̃(k,1) ⟩Al and ⟨h̃(k,1) ⟩Al . e (k) ⟩A = ⟨h e (k,0) ⟩A ∥⟨h e (k,1) ⟩A . e(k) ⟩Al = ⟨g e(k,0) ⟩Al ∥⟨g e(k,1) ⟩Al , ⟨h 13: Pl locally concatenates the shares as ⟨g l l l (k) A (k/2) A (k−1) A (k) A (k/2) A (k−1) A 14: else Pl calculates ⟨g̃ ⟩l = ⟨g̃ ⟩l − ⟨g̃ ⟩l , ⟨h̃ ⟩l = ⟨h̃ ⟩l − ⟨h̃ ⟩l . (k) 15: Pl computes the splitting scores ⟨Lsp ⟩Al using Fmul and Fdiv for all (z, u) based on Eq. (2). (k) (k) 16: Pl gets ⟨z∗ ⟩Al , ⟨u∗ ⟩Al ← Fargmax (⟨Lsp ⟩Al ). (k) (k) (k) 17: Open c ← Fgreater (⟨z∗ ⟩, m − 1) and reveal (z∗ , u∗ ) to Pc , who writes it to OutputΠ c and k to kc . (k) (k) (k,0) B (k,1) B 1 (k,0) B (k,1) B f 18: For k ∈ k0 : Pl runs FBOIS ({⟨{b ⟩0 , ⟨b ⟩0 , (z∗ , u∗ )}, M0 , Tsh }; {{⟨b ⟩1 , ⟨b ⟩1 }, T1ch }) (2k,i) B (2k+1,i) B to get {⟨b ⟩l , ⟨b ⟩l }i∈{0,1} . f 1 , T0 , T0 ) to get {⟨b(2k,i) ⟩B , ⟨b(2k+1,i) ⟩B }i∈{0,1} . 19: For k ∈ k1 : Pl runs FBOIS (now flip the role with M sh ch l l (2k,i) A (2k,i) A 20: For i ∈ {0, 1}: update left-child: ⟨g ⟩l (/⟨h ⟩l ) = Fmux (⟨b(2k,i) ⟩Bl , ⟨g(k,i) ⟩Al (/⟨h(k,i) ⟩Al )). 21: For i ∈ {0, 1}: update right-child: ⟨g(2k+1,i) ⟩Al = ⟨g(k,i) ⟩Al − ⟨g(2k,i) ⟩Al , ⟨h(2k+1,i) ⟩Al = ⟨h(k,i) ⟩Al − ⟨h(2k,i) ⟩Al . 22: Pl computes leaf weights ⟨w⟩Al using Fdiv based on Eq. (3) and writes them in OutputΠ l . ▷ Order-independent 23: For i ∈ {0, 1}: Pl updates ⟨ỹi [j]⟩Al by accumulating Fmux (⟨b(k,i) [j]⟩Bl , ⟨w[k]⟩Al ) (∀j ) over all leaves k . 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⟩Al . One party finally learns the prediction probabilities p on the joint data. Prior protocols often assume PSI-aligned inputs. Evaluation using a secure multiplexer can proceed as follows: i) local traversal: each Pl computes a binary vector b(k,l) (AND-based share ⟨b(k) ⟩Bl in Squirrel) by comparing features with local split criteria; b(k,l) [i] = 1 indicates that sample i may reach node k ; ii) conjunction: the true indicator is b(k) = b(k,0) ∧ b(k,1) , and the tree output is X Fmux (⟨b(k) ⟩Bl , ⟨w[k]⟩Al ). k
To keep inference-time identifiers hidden, we can run circuit-PSI preceding the above procedure, which induces misaligned local indicators. An OPPRF-based synchronization step then aligns indicators across parties: P1 transfers a share of b(k,1) to P0 , yielding aligned shares ⟨b(k,1) ⟩Bl and ⟨b(k,0) ⟩Bl on which Fand applies. The full algorithm is in Appendix C.
5.6. Generalizability Our dual-circuit-PSI framework generalizes to two-party vertical FL (VFL) models that exchange intermediate computations over aligned samples. These models require a data alignment step that, if using standard PSI, leaks sensitive intersection membership. Our framework provides a blueprint for anonymous VFL by replacing this leaky pre-alignment. 1) Anonymous Handshake: It establishes a “symmetric private” alignment in which each party, and only that party, learns its own cuckoo-hash permutation of the intersecting samples, so subsequent computations are performed on the same set of entities without revealing their identities. 2) Synchronization and computation: Pl , with its own secret permutation, re-aligns its local information and continues the computation with the secret shared payload (e.g., completing a forward pass). For data flowing in the reverse direction (e.g., encrypted/noised gradients), our FBOIS can be adapted to securely transfer the aligned information. This workflow can be instantiated in various VFL architectures, e.g., federated transformers [36] and split-NN [37].
TABLE 3. M ICROBENCHMARKS OF AnonGBDT, SINGLE - THREAD
Protocol
instance
7
5
Fargmax Fgreater Fmux FBOIS FBinMatVec 8 Fsigmoid (ours) Fsigmoid [5]
10 106 106 106 1 105 106
Time (s) WAN
Time (s) LAN
Comm. (MB)
4.9 22.2 12.4 12.3 3.7 13.4 31.5
3.0 21.2 1.7 8.4 1.8 4.8 15.5
13.4 81.9 17.5 68.6 29.6 38.4 235.8
Local FastPackLWEs (ours) FastPackLWEs (ours) LWEDimLift + PackLWEs [5] LWEDimLift + PackLWEs [5]
# of inputs 128 512 128 512
Time (s) 0.22 0.87 1.02 3.80
6. Evaluation Parameters: The security parameters are λ = 128, κ = 40. Our designs are implemented in C++ based on Cheetah [38]. We use the stash-less circuit-PSI [15] with 3 hash functions and ϵ = 1.3, and ℓ = 64-bit arithmetic sharing with precision f = 20. For GBDT, α = 0.001 and γ = 0. RLWE is realized using Cheon–Kim–Kim–Song [39] of SEAL 4.1 [40] with p = 2ℓ , N = 8192, N = 4096, Q ≈ 2109 [5]. Testbed: All experiments run on two identical hosts, each with an 8-core 2.5GHz Intel Xeon Platinum 8255C CPU and 64GB RAM under: i) LAN: 1Gbps bandwidth with a latency (ping time) ∼2ms, and ii) WAN: we emulate a 200Mbps link with 20ms latency using the traffic control utility (tc). Metrics: We measure the end-to-end (offline and online) runtime and the total communication costs. Microbenchmarks: Table 3 shows the performance breakdown. Interactive primitives, requiring message exchange between parties, include the protocols for argmax (taking 10 inputs), greater, mux, BOIS, BinMatVec (taking two 105 matrices), and our optimized sigmoid (Section 4.2.3). For local primitives, we compare our FastPackLWEs with Squirrel’s subroutine. Combined with the optimizations (Section 5.4), we achieve a ∼5× runtime speedup.
6.1. Overhead of AnonGBDTOTSA We ran benchmarks on synthetic datasets with varying n, m, and D, using a single thread. Table 4 reports efficiency results. For runtime, AnonGBDTOTSA is consistently faster by ∼3× to 20×, and the gap widens as n, m, or D grows. For communication, our base AnonGBDT scales linearly in n and m, eventually out-of-memory (OOM), due to the OT-heavy Fmux -based gradient aggregation non-batched FOIS . AnonGBDTOTSA removes these bottlenecks, achieving up to 44× lower traffic and avoiding OOM even at the largest dataset sizes tested. 7. Each run with 10 inputs. 8. Input vector size of 128 vector size and matrix size of 128 × 105 .
TABLE 4. E FFICIENCY OF AnonGBDT (n = n0 = n1 = 105 , m = 50, B = 16, D = 5, SINGLE THREAD )
Parameters WAN Time (s) LAN Time (s) Base Final Base Final n = 100K 3873.5 195.2 567.0 112.5 n = 250K OOM 346.5 OOM 227.0 n = 500K OOM 602.6 OOM 422.2 n = 1M OOM 1120.9 OOM 817.1 D=3 1077.0 72.3 142.8 37.3 D=4 1999.2 117.1 271.2 64.5 D=6 7462.7 357.6 1024.6 203.6 m = 10 969.2 91.2 144.0 36.9 m = 25 2061.5 131.1 303.1 67.1 m = 100 OOM 334.0 OOM 214.1
Comm. (GB) Base Final 26.1 0.6 OOM 1.1 OOM 2.1 OOM 4.0 6.6 0.2 13.1 0.4 51.8 0.9 5.5 0.4 13.2 0.5 OOM 0.7
TABLE 5. E FFICIENCY OF AnonGBDT FOR n0 ̸= n1 (n1 = 105 , m = 50, B = 16, D = 5, SINGLE THREAD )
Size n0 0.10n1 0.20n1 0.50n1 0.75n1 1.00n1
WAN Time (s) Base Final 439.3 98.5 780.4 105.6 2156.3 138.8 3047.2 167.4 3873.5 195.2
LAN Time (s) Base Final 72.4 49.1 121.3 54.5 267.4 69.7 413.8 87.3 567.0 112.5
Comm. (GB) Base Final 3.4 0.34 5.6 0.37 15.2 0.45 21.3 0.54 26.1 0.6
AnonGBDT is also evaluated under unbalanced settings (n0 ̸= n1 ), as shown in Table 5. The base design benefits more than AnonGBDTOTSA , with LAN speedups of 1.5−5× as the imbalance ratio ( nn01 ) decreases. This is because AnonGBDTOTSA must run FBOIS , Fsigmoid twice, processing to align with each party’s inputs separately.
6.2. Comparisons with Prior Arts Efficiency: AnonGBDTOTSA is evaluated on the same hardware as Squirrel [5], across two hosts with 8 CPU cores each. Pivot [8] and HEP-XGB [7] were evaluated under more favorable conditions (e.g., 32 cores for HEP-XGB) and heterogeneous network settings; we quoted their reported results in Table 6. Despite the stronger privacy guarantees (no identifier leakage), our runtime is only ∼0.7×–1.7× that of Squirrel and remains competitive with the other less private schemes (which would require prohibitively costly generic tools for similar privacy). Effectiveness: We train models via AnonGBDTOTSA on six public datasets [41] and evaluate with our inference protocol ΠInfer in Figure 13. XGBoost [42] serves as a plaintext baseline. Using 5-fold cross-validation, T = 10 trees, and depth D = 5, we attain the highest F1 score across all tasks (Table 7), primarily due to our improved sigmoid approximation (Section 4.2.3).
6.3. Scalability We assess scalability by running AnonGBDTOTSA with eight threads (unlike the settings for comparison in Section 6.2) on synthetic datasets that vary in sample count n, 9. Pivot [8] uses 32 cores. Numbers of threads follow prior works [5].
Time (LAN) vs. Sample size n
Time (WAN) vs. Sample size n Figure 10. Scalability of AnonGBDT
OTSA
Time (LAN) vs. Depth D
Time (LAN) vs. Feature size m0 = m1
Time (WAN) vs. Depth D
Time (WAN) vs. Feature size m0 = m1
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 Ours [5] [8] Ours [5] [8] Ours [5] [7] Ours [5] [7]
Parameters n = 5 × 104 D = 4, B = 8 m0 = 8, m1 = 7 n = 2 × 105 D = 4, B = 8 m0 = 8, m1 = 7 n = 1.4 × 105 D = 5, B = 10 m0 = 7, m1 = 16 n = 1.4 × 105 D = 5, B = 10 m0 = 7, m1 = 16
Settings LAN 6 threads LAN 6 threads LAN 32 threads9 100Mbps 32 threads9
Time (s) 39.0 60.0 1680.0 96.5 111.0 448.0 139.1 114.0 476.0 668.7 400.0 1510.0
TABLE 7. F1 SCORE COMPARISON
Dataset
Ours
Squirrel
Pivot
breast-cancer phishing a9a cod-rna skin nonskin covtype.binary
0.920 0.957 0.654 0.882 0.988 0.782
0.917 0.957 0.651 0.402 0.742 0.556
0.919 0.957 0.653 0.408 0.743 0.572
HEPXGB 0.889 0.951 0.643 0.403 0.741 0.552
XGBoost 0.947 0.961 0.654 0.882 0.989 0.796
feature count m, and tree depth D. Figure 10 reports runtime and traffic; Squirrel’s numbers are directly quoted. Thanks to FastPackLWEs and the other engineering optimizations (Section 5.4), our LAN runtime is on par with
Squirrel. Because the improved sigmoid scales sublinearly with n, our scheme grows more gracefully as the sample size increases. Communication rises linearly with n, but its growth with m and D is markedly flatter: i) dual-circuitPSI allows us to use the communication-friendly FBinMatVec , keeping the cost in m low, and ii) our FBOIS reduces the indicator-sync complexity from O(2D ) to O(D). Under WAN conditions, runtime is 2–4× higher than in LAN, consistent with the added latency and reduced bandwidth.
7. Discussion 7.1. Gradient-based One-Side Sampling (GOSS) LightGBM [23] accelerates histogram construction by prioritizing “informative” samples with large (firstorder) gradient magnitudes. Given the per-sample gradients {gi }ni=1 at a node, GOSS first sorts the samples by |gi | in descending order. It keeps the top fraction a (high-gradient set H) intact. From the remaining set L, it randomly samples a fraction b. To correct the sampling bias, it multiplies the gradients and Hessians of the sampled low-gradient points by (1 − a)/(1 − b) before building the histogram. This reduces the working-set size from the sample size n to |H| + b|L|, speeding up training in the plaintext setting. Limitations in Secure Two-party Computation: Identifying H requires an oblivious sort of the secret-shared gradients, which costs O(n log n) time and substantial bandwidth (cf., ∼4GB for one million records with ℓ = 32 [43]). The subsequent random sampling must also be oblivious, adding
further overhead. Consequently, the gains of GOSS in the clear are outweighed by the expense of these secure primitives, making it unsuitable for our secure GBDT pipeline.
7.2. Private-ID Private-ID protocols [17], [44] return pseudo-random (or secret-shared) identifiers for the intersection, rather than a Boolean mask over all records (even those not in the intersection) as in circuit-PSI. They have two limitations. Cardinality leakage: They explicitly reveal |ID0 ∩ ID1 |, whereas circuit-PSI does not. Hiding |ID0 ∩ ID1 | motivates threshold PSI designs [45] that return intersection only if its size exceeds a threshold, whereas prior threshold PSI protocols may leak this size. Loss of ordering: Neither party learns how the output IDs align with its local feature matrix M; otherwise, the true IDs could be inferred from the feature order. As a result, any subsequent operations must operate on secret-shared versions ⟨M⟩Bl . For secure GBDT, this means gradient histograms must be built with the OT-heavy multiplexer, replicating the inefficiency of our base design. In contrast, circuit-PSI reveals the ID-feature correspondence to the receiver. With our elaborated dual-circuit-PSI design, both parties possess a plaintext copy of their own M aligned to the intersection, enabling both sides to use the more communication-efficient FBinMatVec .
7.3. Hiding the Splits All known secure two-party decision-tree protocols, including ours (with data alignment hidden), reveal the best splits at internal nodes [5], [7], [8], [46], a leakage previously noted [47]. A recent work [48] attempts to mitigate this by obliviously permuting the raw matrix M to ⟨M′ ⟩A , secret-sharing a one-hot vector ⟨s⟩A for the chosen bin, and revealing, for each sample i, the indicator Is [i] = M′ [i] · s that determines the branch. Since the permutation is hidden, the split index is assumed private. Yet, the protocol leaks |ID0 ∩ ID1 | and enables each party to correlate revealed f , allowing left/right counts with its own prefix matrix M recovery of the feature/bin and contradicting privacy claims. A direct remedy is to keep split indices secret-shared. Three-party designs [49], [50], [51] realize this via groupbased data structures and per-layer oblivious sorting, but such sorting is prohibitively expensive with two parties. Devising an efficient 2-party variant remains an open problem.
8. Related Work Some federated-learning (FL) frameworks target private GBDT training. SecureBoost(+) [52] employs Paillier homomorphic encryption, and VF2 Boost [53] refines the pipeline for large datasets. They only protect the gradient aggregation, leaving internal artifacts, including split points, leaf updates, etc., in plaintext. Such leakage enables inference attacks [54], [55], for instance, if an income feature
determines a split, a party lacking that feature can deduce a sample’s income range from its branch assignment. Takahashi et al. [55] use local differential privacy to curb label leakage. Although computationally light, differential privacy adds noise that trades accuracy for privacy. Secure multiparty computation has been widely adopted. Lindell and Pinkas [46] propose secure multiparty computation for decision-tree training using garbled circuits and OT. Hoogh et al. [56] use secret sharing for multiparty GBDT training. Abspoel et al. [57] propose an oblivious sorting network for GBDT training with continuous feature values. Due to high communication costs, these designs are inefficient for large datasets. Solutions using function secret sharing [6], [58] achieve efficient online decision tree training, but they require offline correlated random number generation to support secure multiplication. The most relevant work [5], [7], [8] to ours is the hybrid approaches. Pivot [8] incorporates threshold Paillier HE and secret sharing for tree training. Fang et al. [7] propose private large-scale XGBoost training. However, their scheme heavily relies on a semi-honest third party, e.g., trusted execution environments; otherwise, the performance will degrade significantly. Squirrel [5] improves the histogramcalculation efficiency via RLWE-based (instead of Paillier) HE and proposes a new method to approximate the sigmoid function using a Fourier series. Instead, its follow-up [59] realizes pick-then-sum with pure secret sharing, shifting most costs to an offline phase. See the systematization of Chatel et al. [60] for related results, including earlier work. Some selected schemes develop anonymous vertical FL. Sun et al. [61] suggest using private set union instead of PSI to obscure the common IDs and generating synthetic features for samples outside the intersection, which can degrade model accuracy. OpenVFL [62] proposes a labeled PSI that returns only homomorphically encrypted features within the intersection. This conceals the common elements and confines the subsequent training to the encrypted domain under homomorphic encryption, which is costly when GBDT pays heavily for secure comparisons. OpenVFL [62] implemented logistic regression only and is not open source.
9. Conclusion Existing private GBDT protocols run standard PSI once to align the two datasets on their intersection, then train on the aligned records, which inevitably discloses the intersection. Circuit-PSI can avoid this leakage in principle, but its asymmetric interface clashes with order-dependent training flows, and embedding the training loop as a generic circuit makes it impractically slow. We introduce AnonGBDT, the first anonymous GBDT framework. The base variant adds two new primitives: FOIS for indicator synchronization, and Fmux -based gradient aggregation. Although more private, it incurs considerable communication and memory overheads. Our final scheme AnonGBDTOTSA resolves these bottlenecks through a dual-circuit-PSI architecture that symmetrizes ownership of the ID-feature mapping. It enables
efficient FBinMatVec aggregation, further accelerated by our FastPackLWEs subroutine. Moreover, we propose a batched OPPRF-based OIS protocol. Empirically, AnonGBDTOTSA is up to an order of magnitude faster than the base design. Beyond GBDT, our dual-circuit-PSI can integrate with other vertical-learning frameworks, e.g., Split-NN [37], to add anonymity at modest overheads.
[18] J. P. K. Ma and S. S. M. Chow, “Secure-computation-friendly private set intersection from oblivious compact graph evaluation,” in AsiaCCS, 2022, pp. 1086–1097.
References
[21] 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,” in NDSS, 2021.
[1]
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.
[19] 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. [20] H. Chen, W. Dai, M. Kim, and Y. Song, “Efficient homomorphic conversion between (ring) LWE ciphertexts,” in ACNS, 2021, pp. 460– 479.
[22] T. Chen and C. Guestrin, “XGBoost: A scalable tree boosting system,” in KDD, 2016, pp. 785–794.
[2]
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.
[23] 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,” in NeurIPS, 2017, pp. 3146–3154.
[3]
X. Ling, W. Deng, C. Gu, H. Zhou, C. Li, and F. Sun, “Model ensemble for click prediction in Bing search ads,” in WWW (Companion), 2017, pp. 689–698.
[24] D. Demmler, T. Schneider, and M. Zohner, “ABY - A framework for efficient mixed-protocol secure two-party computation,” in NDSS, 2015.
[4]
L. K. L. Ng and S. S. M. Chow, “SoK: Cryptographic neural-network computation,” in S&P, 2023, pp. 497–514.
[25] D. Beaver, “Efficient multiparty protocols using circuit randomization,” in CRYPTO, 1991, pp. 420–432.
[5]
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,” in USENIX Security, 2023, pp. 6435– 6451.
[26] O. Catrina and A. Saxena, “Secure computation with fixed-point numbers,” in FC, 2010, pp. 35–50.
[6]
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.
[7]
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 learning,” in CIKM, 2021, pp. 443–452.
[8]
Y. Wu, S. Cai, X. Xiao, G. Chen, and B. C. Ooi, “Privacy preserving vertical federated learning for tree-based models,” Proc. VLDB Endow., vol. 13, no. 11, pp. 2090–2103, 2020.
[9]
M. J. Freedman, K. Nissim, and B. Pinkas, “Efficient private matching and set intersection,” in EUROCRYPT, 2004, pp. 1–19.
[10] V. Kolesnikov, R. Kumaresan, M. Rosulek, and N. Trieu, “Efficient batched oblivious PRF with applications to private set intersection,” in CCS, 2016, pp. 818–829. [11] 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. [12] 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,” in EuroS&P, 2020, pp. 370–389.
[27] V. Kolesnikov, A. Sadeghi, and T. Schneider, “Improved garbled circuit building blocks and applications to auctions and computing minima,” in CANS, 2009, pp. 1–20. [28] M. O. Rabin, “How to exchange secrets with oblivious transfer,” IACR Cryptol. ePrint Arch. 2005/187, 2005. [29] K. Yang, C. Weng, X. Lan, J. Zhang, and X. Wang, “Ferret: Fast extension for correlated OT with small communication,” in CCS, 2020, pp. 1607–1626. [30] Z. Brakerski and V. Vaikuntanathan, “Fully homomorphic encryption from ring-lwe and security for key dependent messages,” in CRYPTO, 2011, pp. 505–524. [31] R. Canetti, “Security and composition of multiparty cryptographic protocols,” J. Cryptol., vol. 13, no. 1, pp. 143–202, 2000. [32] Y. Zheng, Q. Zhang, S. S. M. Chow, Y. Peng, S. Tan, L. Li, and S. Yin, “Secure softmax/sigmoid for machine-learning computation,” in ACSAC, 2023, pp. 463–476. [33] A. Y. L. Kei and S. S. M. Chow, “SHAFT: Secure, handy, accurate, and fast transformer inference,” in NDSS, 2025. [34] A. Amit, P. Stanislav, R. Mariana, S. Phillipp, and S. Karn, “Communication-efficient secure logistic regression,” in EuroS&P, 2024, pp. 440–467. [35] 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.
[13] B. Pinkas, T. Schneider, O. Tkachenko, and A. Yanai, “Efficient circuit-based PSI with linear communication,” in EUROCRYPT Part III, 2019, pp. 122–153.
[36] Z. Wu, J. Hou, Y. Diao, and B. He, “Federated transformer: Multiparty vertical federated learning on practical fuzzily linked data,” in NeurIPS, 2024.
[14] P. Rindal and P. Schoppmann, “VOLE-PSI: Fast OPRF and circuitPSI from vector-OLE,” in EUROCRYPT Part II, 2021, pp. 901–930.
[37] O. Gupta and R. Raskar, “Distributed learning of deep neural network over multiple agents,” J. Netw. Comput. Appl., vol. 116, pp. 1–8, 2018.
[15] S. Raghuraman and P. Rindal, “Blazing fast PSI from improved OKVS and subfield VOLE,” in CCS, 2022, pp. 2505–2517.
[38] SecretFlow, “Cheetah: Lean and fast secure two-party deep neural network inference,” https://github.com/secretflow/spu/tree/main/ libspu/mpc/cheetah, 2024.
[16] J. H. M. Ying, S. Cao, G. S. Poh, J. Xu, and H. W. Lim, “PSIStats: Private set intersection protocols supporting secure statistical functions,” in ACNS, 2022, pp. 585–604. [17] G. Garimella, P. Mohassel, M. Rosulek, S. Sadeghian, and J. Singh, “Private set operations from oblivious switching,” in PKC Part II, 2021, pp. 591–617.
[39] J. H. Cheon, A. Kim, M. Kim, and Y. S. Song, “Homomorphic encryption for arithmetic of approximate numbers,” in ASIACRYPT Part I, 2017, pp. 409–437. [40] K. Laine, “Microsoft SEAL (release 4.1),” https://github.com/ Microsoft/SEAL, 2023, Microsoft Research, Redmond, WA, USA.
[41] C.-J. Lin, “LIBSVM data: Classification (binary class),” https://www. csie.ntu.edu.tw/∼cjlin/libsvmtools/datasets/binary.html, 2024. [42] D. D. M. L. Community, “eXtreme gradient boosting,” https://github. com/dmlc/xgboost, 2024. [43] S. Peceny, S. Raghuraman, P. Rindal, and H. Shah, “Efficient permutation correlations and batched random access for two-party computation,” in PKC Part IV, 2025, pp. 76–109. [44] P. Buddhavarapu, A. Knox, P. Mohassel, S. Sengupta, E. Taubeneck, and V. Vlaskin, “Private matching for compute,” IACR Cryptol. ePrint Arch. 2020/599, 2020. [45] Y. Zhao and S. S. M. Chow, “Can you find the one for me?” in WPES, co-located with CCS, 2018, pp. 54–65. [46] Y. Lindell and B. Pinkas, “Privacy preserving data mining,” in CRYPTO, 2000, pp. 36–54. [47] Z. Zhu and W. Du, “Understanding privacy risk of publishing decision trees,” in DBSec, 2010, pp. 33–48. [48] 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. [49] K. Hamada, D. Ikarashi, R. Kikuchi, and K. Chida, “Efficient decision tree training with new data structure for secure multi-party computation,” Proc. Priv. Enhancing Technol, pp. 343–364, 2023. [50] D. Bhardwaj, S. Saravanan, N. Chandran, and D. Gupta, “Securely training decision trees efficiently,” in CCS, 2024, pp. 4673–4687. [51] 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,” in CCS, 2024, pp. 4376–4390. [52] 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. [53] F. Fu, Y. Shao, L. Yu, J. Jiang, H. Xue, Y. Tao, and B. Cui, “VF2 Boost: Very fast vertical federated gradient boosting for crossenterprise learning,” in SIGMOD, 2021, pp. 563–576. [54] 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,” in USENIX Security, 2022, pp. 1397–1414. [55] H. Takahashi, J. Liu, and Y. Liu, “Eliminating label leakage in treebased vertical federated learning,” arXiv:2307.10318, 2023. [56] S. de Hoogh, B. Schoenmakers, P. Chen, and H. op den Akker, “Practical secure decision tree learning in a teletreatment application,” in FC, 2014, pp. 179–194. [57] M. Abspoel, D. Escudero, and N. Volgushev, “Secure training of decision trees with continuous attributes,” Proc. Priv. Enhancing Technol., vol. 2021, no. 1, pp. 167–187, 2021. [58] Y. Jiang, F. Mei, T. Dai, and Y. Li, “SiGBDT: Large-scale gradient boosting decision tree training via function secret sharing,” in AsiaCCS, 2024, pp. 274–288. [59] 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,” in Deep Learning Security and Privacy (DLSP) Workshop, co-located with S&P, 2024, pp. 95–103.
[63] D. Rathee, T. Schneider, and K. K. Shukla, “Improved multiplication triple generation over rings via RLWE-based AHE,” in CANS, 2019, pp. 347–359. [64] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(Leveled) fully homomorphic encryption without bootstrapping,” ACM Trans. Comput. Theory, vol. 6, no. 3, pp. 13:1–13:36, 2014. [65] C. Zhang, Y. Chen, W. Liu, M. Zhang, and D. Lin, “Linear private set union from multi-query reverse private membership test,” in USENIX Security, 2023, pp. 337–354.
Appendix A. Optimizations in Sigmoid A.1. Secure Decimal Multiplication for Trigonometric Functions Fmul relies on Beaver triples [25] for a · b = c in secret shares, which can be efficiently implemented in RLWEbased HE [63], e.g., Brakerski–Gentry–Vaikuntanathan [64]. Specifically, P0 generates random a ←$ Z264 and sends ciphertext JaK to P1 . P1 generates another random b ←$ Z264 and gets JcK = JaK · b. However, the ciphertext length N is usually 8192, and the plaintext modulus is no more than a 32-bit prime number (for efficient homomorphic operations), which cannot encode c with a bit size of 128 to fit Z264 . The literature [63] solves this by splitting the large Q plaintext modulus p into four smaller pi where p = pi via the Chinese remainder theorem (CRT). Four instances (with modulus pi respectively) of the above protocol are executed to get outputs c0 , . . . , c3 , which can be combined into the output c (with modulus p) via CRT and then truncated into Z264 . Note that each pi corresponds to Q of bit size. In our Fsigmoid , the range of floating numbers sin(x), cos(x), and sin(x) · cos(x) are all within [−1, 1] (encoded as [−2f , 2f ]). Recalling the average error of our sigmoid approximation is 0.002, we can set f = 15 in multiplication. Therefore, the plaintext modulus when encrypting sin(x) and cos(x) can be less than 232 , using only one p instead of four pi . The communication/computation cost of one Fmul in Fsigmoid is now only 1/4 of the original Fmul .
A.2. Configuration of Fourier Series We use the following coefficients and parameters a0 = 0.5, a2 = −1.070336,
a1 = 1.642327, a3 = 0.5510985,
[60] 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.
and L = 3 such that the Fourier series output is bounded by 1 within [−5.6, 5.6]. Figure 11 shows the comparison between our sigmoid with Squirrel and the ground truth.
[61] J. Sun, X. Yang, Y. Yao, A. Zhang, W. Gao, J. Xie, and C. Wang, “Vertical federated learning without revealing intersection membership,” arXiv:2106.05508, 2021.
A.3. Complexity Comparison
[62] 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 learning framework with stronger privacy-preserving,” IEEE Trans. Inf. Forensics Secur., vol. 19, pp. 9670–9681, 2024.
Table 8 compares our Fsigmoid with the corresponding protocol of Squirrel. With λ = 128, f = 20, and δ = 4, our total communication is 2, 976 bits (vs. 19, 816 for Squirrel).
Functionality FBOIS (k)
(k)
Pc ’s Input: {(z∗ , u∗ )}k∈k , {⟨b(k,0) ⟩Bc , ⟨b(k,1) ⟩Bc }k∈k , f c , and the simple hash table T1−c . M sh P1−c ’s Input: {⟨b(k,0) ⟩B1−c , ⟨b(k,1) ⟩B1−c }k∈k , and the cuckoo hash table T1−c ch . Public parameters: A set of nodes k to be synchronized Output: {⟨b(2k,i) ⟩B , ⟨b(2k+1,i) ⟩B }i∈{0,1},k∈k .
Protocol ΠBOIS 1: for each node k ∈ k do (k,c) 2: Pc samples ⟨b∗ ⟩Bc = rc ←$ {0, 1}(1+ϵ)n .
Figure 11. Comparison of sigmoid approximations TABLE 8. A MORTIZED BIT COMMUNICATION ( COMM .) COMPLEXITY COMPARISON OF Fsigmoid BETWEEN OURS AND S QUIRREL’ S
Fsigmoid Comm. complexity of Fmul Comm. complexity of two Fgreater # of terms in Fourier series Comm. complexity of Fsigmoid
(k,c) f c [z∗(k) B + u(k) Pc sets b∗ =M ∗ ]. (k,c) (k,c) 4: Pc shares ⟨b∗ ⟩B1−c ← b∗ ⊕ rc with P1−c . (k,c) B (2k,c) B 5: Pl : ⟨b ⟩l = Fand (⟨b∗ ⟩l , ⟨b(k,c) ⟩Bl ) (2k+1,c) B and ⟨b ⟩l = ⟨b(2k,c) ⟩Bl ⊕ ⟨b(k,c) ⟩Bl . 6: Pc samples r1−c ←$ {Z2|k| }(1+ϵ)n , and initializes e ′ = 0(1+ϵ)n . packed assignment b ∗ 7: for each node k ∈ k do (k,c) 8: Pc “reorders” b∗ to b′∗ to align with IDc . ′ ′ e e 9: Pc packs b∗ = b∗ ⊕ (b′∗ ≪ k). (k,1−c) B 10: Pc sets ⟨b∗ ⟩c = (r1−c ≫ k)&1(1+ϵ)n . 11: ∀j ∈ [0, e), ∀i ∈ [0, (1 + ϵ)n): 1−c e′ ′ [i]}, and Pc sets a table T = {(T1−c sh [i, j], b∗ [i ]⊕r IDc [i′ ] is placed in T1−c [i, j] via simple hashing. sh 1−c e (1−c) 12: Pl runs FOPPRF ({T}, {Tch }); P1−c gets b ∗ 13: for each node k ∈ k do (k,1−c) B e (1−c) 14: P1−c : ⟨b∗ ⟩1−c = (b ≫ k)&1(1+ϵ)n . ∗ (k,1−c) 15: Pl :⟨b(2k,1−c) ⟩Bl = Fand (⟨b∗ ⟩Bl , ⟨b(k,1−c) ⟩Bl ). (2k+1,1−c) B (2k,1−c) B 16: Pl :⟨b ⟩l = ⟨b ⟩l ⊕ ⟨b(k,1−c) ⟩Bl .
3:
Ours
Squirrel
288
288 · 4
≈1384 − 4 log2 ⌊ f −δ ⌋ 4 −32⌊ f −δ ⌋ 4
≈1384
4
9
⌋ ≈1384 − 4 log2 ⌊ f −δ 4 −32⌊ f −δ ⌋ + 288 · 6 4
≈1384 + 288 · 4 · 16
Appendix B. Batched OPPRF-based OIS (BOIS) The functionality and protocol of batched OPPRF-based BOIS are shown in Figure 12. For completeness, we note an alternative realization of FBOIS via oblivious transfer for a sparse array (OTSA) [35], which provides an alternative view of the OPPRF step as a sparse-array transfer. Namely, it stores the programmed shares at the same bucket-index domain and uses fixedlength fillers sampled from the output range. For comparison of array-transfer abstractions, Zhang et al. [65] compare OTSA with oblivious keyvalue stores [15] and observe that OTSA additionally hides the query-to-output correspondence.
Figure 12. Ideal functionality and protocol of BOIS
Theorem D.1. ΠOIS (Figure 3) is a secure protocol, which follows Definition 3.1 under (FOT , Fand )-hybrid.
1) If (z∗ , u∗ ) is owned by P0 , S receives ⟨b∗ ⟩B1 from P0 f 0 [z∗ B +u∗ ]; (Line 3). Then S computes ⟨b∗ ⟩B0 = ⟨b∗ ⟩B1 ⊕ M else S plays the sender of FOT with input of the XOR of f 1 ⟩B as in Line 8. randomly chosen r(= ⟨b∗ ⟩B0 ) and ⟨M 0 2) S plays the role of Fand with inputs of ⟨b∗ ⟩B0 , ⟨b⟩B0 to obtain ⟨bL ⟩B0 , then sets ⟨bR ⟩B0 = ⟨bL ⟩B0 ⊕ ⟨b⟩B0 as Line 11. To prove the simulation is indistinguishable from the real protocol, we consider the following hybrids. Hybrid0 . The same as the real protocol. Hybrid1 . Lines 8–9 in Protocol ΠOIS use replaced FOT . Hybrid2 . Line 11 in Protocol ΠOIS uses replaced Fand . Hybrid3 . The same as the execution of S above. Note that Hybrid1 ≈c Hybrid0 as FOT is secure, and Hybrid2 ≈c Hybrid1 as Fand is secure. Hybrid3 is Hybrid0 identical to Hybrid2 . Therefore, S ≈c V0 . Case 2: P1 is corrupted: The simulator S plays the role P0 , and the interaction with P1 is similar to the above. In short, in both cases, the FOT , Fand -hybrid ΠOIS protocol is secure in the semi-honest model.
Proof for Theorem D.1 (Sketch). Case 1: P0 is corrupted: The simulator S interacts with P0 as follows.
Proof for Theorem 5.1 (Sketch). Case 1: The sender Pc is corrupted: The simulator S interacts with Pc as follows.
Appendix C. Anonymous Batch Inference The functionality and the protocol of our anonymous batch inference are shown in Figure 13.
Appendix D. Security Proof
Functionality FInfer P0 ’s Input: ID0 , X0 , best split C0 , weight share ⟨w⟩A0 . P1 ’s Input: ID1 , X1 , best split C1 , weight share ⟨w⟩A1 . Output: Prediction probability p to P0 .
Protocol ΠInfer 1: Jointly invoke ⟨q⟩B l
← FCPSI ({ID0 }, {ID1 }), P0 runs as receiver with cuckoo hash table Tch , P1 runs as sender with simple hash table Tsh . 2: for tree t ∈ Tt do 3: Pl sets root node’s indicator b(0, l) = 1(1+ϵ)n 4: for internal node k ∈ [1, 2D−1 ), each sample i do 5: if Cl [k] is not ⊥ then (k) (k) 6: Pl gets (z∗ , u∗ ) ← Cl [k] (k) (k) (k) 7: if Xl [i, z∗ ] ≤ split value of z∗ , u∗ then (2k,l) (k,l) 8: Pl : b [i] = b [i]. 9: Pl : b(2k+1,l) [i] = 0. 10: else 11: Pl : b(2k,l) [i] = 0. (k,l) 12: Pl : b(2k+1,l) [i] = bl [i]. 13: else Pl : b(2k,l) [i] = b(2k+1,l) [i] = b(k,l) [i] 14: P0 shares b(0) , Pl gets ⟨b(0) ⟩Bl . 15: P1 : sets r ←$ {Z2#leaves }(1+ϵ)n , and extracts ⟨b(k,1) ⟩B1 which is the k − 2D−1 -th bit of r. e′ 16: P1 packs all the leaves’ indicators b(k,1) as b 17: ∀i ∈ [0, (1 + ϵ)n), ∀j ∈ [0, e), P1 creates a table e ′ [i′ ] ⊕ r[i])} where ID[i′ ] is T = {(Tsh [i, j], b placed in Tsh via simple hashing. e ′′ . 18: Pl runs FOPPRF ({T}, {Tch }); P0 gets b B (1+ϵ)n 19: Pl initializes ⟨S⟩l = 0 20: for node k ∈ {2D−1 , . . . , 2D − 1} do 21: Pl extract indicator ⟨b(k,1) ⟩Bl which is the (k − e ′′ . 2D−1 )-th bit of b (k) B 22: Pl : ⟨b ⟩l = Fand (⟨b(k,0) ⟩Bl , ⟨b(k,1) ⟩Bl ) 23: Pl : ∀i ∈ [0, (1 + ϵ)n), ⟨S[i]⟩Al = ⟨S[i]⟩Al + Fmux (⟨b(k) [i]⟩Bl , ⟨w[k]⟩Al ) B A 24: Pl : ⟨ỹ⟩A l = Fmux (⟨q⟩l , ⟨S⟩l ) 25: P0 recovers ỹ and gets p = sigmoid(ỹ). Figure 13. Functionality and protocol of Inference (k,c)
1) ∀k ∈ k, S receives ⟨b∗ ⟩B1−c from Pc and computes rc (k) (k) f c . Then S sets ⟨b(k,c) ⟩Bc = rc and with (z∗ , u∗ ) and M ∗ (k,c) B (k,c) B ⟩c . After plays the role of Fand with ⟨b∗ ⟩c and ⟨b obtaining ⟨b(2k,c) ⟩Bc , S computes ⟨b(2k+1,c) ⟩Bc as Lines 2–5. 2) S constructs {T} and ⟨bk,1−c ⟩Bc (∀k ∈ k) as Lines 6–11. ∗ Then S plays the role of FOPPRF with {T}. (k,1−c) B 3) ∀k ∈ k, S plays the role of Fand with inputs ⟨b∗ ⟩l (k,1−c) B 2k+1,1−c B and ⟨b ⟩l , and obtain ⟨b ⟩c as Line 15. Finally, S computes ⟨b2k+1,1−c ⟩Bc as Line 16. For indistinguishable simulation, we consider: Hybrid0 . The same as the real protocol. Hybrid1 . Line 5 in ΠBOIS uses replaced Fand .
Hybrid2 . Line 12 uses replaced FOPPRF . Hybrid3 . Lines 15–16 use replaced Fand . Hybrid4 . The same as the execution of S above. Note that Hybrid1 ≈c Hybrid0 as Fand is secure; Hybrid2 ≈c Hybrid1 as FOPPRF is secure; Hybrid3 ≈c Hybrid2 as Fand is secure; Hybrid4 is identical to Hybrid0 Hybrid3 . Therefore, S ≈c Vc . Case 2: The receiver P1−c is corrupted: S plays the role of Pc and interacts with P1−c like Case 1 except: 1) S ignores the process of Lines 2–4, and chooses ran(k,c) domly ⟨b∗ ⟩B1−c (∀k ∈ k) and sends to P1−c . 2) S ignores the process of Lines 6–11, and plays the role e 1−c as FOPPRF with input T1−c ch to obtain b∗ . Then S extracts (k,1−c) B ⟨b∗ ⟩1−c ∀k ∈ k as Line 14. In short, in both cases, the Fand , FOPPRF -hybrid ΠBOIS protocol is secure in the semi-honest model.
Proof for Theorem 5.2 (Sketch). Case 1: P0 is corrupted: The simulator S interacts with P0 as follows. 1) S plays the sender and receiver of two FCPSI with {ID0 , y}, respectively, as Lines 2–3. Then S obtains ⟨b(1,0) ⟩B0 , ⟨y0 ⟩A0 , ⟨b(1,1) ⟩B0 and ⟨y1 ⟩A0 . 2) For tree t ∈ Tt , S plays the role of Fsigmoid , Fmul , and Fmux with input ⟨b(1,i) ⟩B0 and ⟨yi ⟩A0 to derive the gradients ⟨g(1,i) ⟩A0 , ⟨h(1,i) ⟩A0 , for i ∈ {0, 1} as Lines 5–6. 3) ∀ internal node k of tree t, if k is a root/left node, S plays the role of FBinMatVec alternately to obtain ⟨g̃(k,i) ⟩A0 ||⟨h̃(k,i) ⟩A0 for i ∈ {0, 1}, which are concatenated e (k) ⟩A as Line 14. e(k) ⟩A0 and ⟨h as Line 13; else S calculates ⟨g 0 4) ∀ internal node k of tree t, S plays the role of Fmul and Fdiv with ⟨g̃(k) ⟩A0 , ⟨h̃(k) ⟩A0 to obtain ⟨Lsp ⟩A0 as Line 15. 5) ∀ internal node k of tree t, S plays the role of Fargmax (k) (k) with input ⟨Lsp ⟩A0 to obtain ⟨z∗ ⟩A0 and ⟨u∗ ⟩A0 as Line 16. 6) ∀ internal node k of tree t, S plays the role of Fgreater (k) with inputs ⟨z∗ ⟩A0 to obtain ⟨c⟩B0 , and then open c to (k) (k) recovery z∗ and u∗ to Pc , which is exactly equal to the programmed outputs in real execution when c = 0. Finally, S appends k into kc as Line 17. 7) ∀ level d in tree t, S plays the role of FBOIS to obtain {⟨b(2k,i) ⟩B0 , ⟨b(2k+1,i) ⟩B0 }k∈ki ,i∈{0,1} as Lines 18–19. 8) S plays the role of Fmux with the inputs ⟨b(2k,i) ⟩B0 , ⟨g(k,i) ⟩A0 and ⟨h(k,i) ⟩A0 to update the gradients of left child nodes ⟨g(2k,i) ⟩A0 , ⟨h(2k,i) ⟩A0 . Then update the gradients of right child nodes as Line 21. 9) For tree t, S plays the role of Fdiv with inputs ⟨g(k,0) ⟩A0 , ⟨h(k,0) ⟩A0 to obtain the weight ⟨w⟩A0 as Line 22. 10) For tree t, S plays the role of Fmux with inputs ⟨b(k,i) ⟩B0 , ⟨w[k]⟩A0 to update ⟨ỹi ⟩A0 (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. OTSA Hybrid1 . Lines 2–3 (ΠGBDT ) use replaced FCPSI . Hybrid2 . Lines 5–6 use replaced Fsigmoid , Fmul , Fmux . Hybrid3 . Lines 11–12 use replaced FBinMatVec . Hybrid4 . Line 15 use replaced Fmul and Fdiv . Hybrid5 . Line 16 uses replaced Fargmax .
Hybrid6 . Line 17 uses replaced Fgreater . Hybrid7 . Lines 18–19 use replaced FBOIS . Hybrid8 . Line 20 uses replaced Fmux . Hybrid9 . Line 22 uses replaced Fdiv . Hybrid10 . Line 23 uses replaced Fmux . Hybrid11 . The same as the execution of S above. Note that Hybrid1 ≈c Hybrid0 as FCPSI is secure; Hybrid2 ≈c Hybrid1 as Fsigmoid and Fmul are secure; Hybrid3 ≈c Hybrid2 as FBinMatVec is secure based on the semantic security of RLWE ciphertexts; Hybrid4 ≈c Hybrid3 as Fmul and Fdiv is secure; Hybrid5 ≈c Hybrid4 as Fargmax is secure; Hybrid6 ≈c Hybrid5 (k) (k) as Fgreater is secure, and the recovered z∗ and u∗ are programmed into ideal functionality as the identical output between real execution and simulation; Hybrid7 ≈c Hybrid6 as FBOIS is secure; Hybrid8 ≈c Hybrid7 as Fmux is secure; Hybrid9 ≈c Hybrid8 as Fdiv is secure; Hybrid10 ≈c Hybrid9 as Fmux is secure. Hybrid11 is Hybrid0 identical to Hybrid10 . Thus, S0 ≈c V0 . Case 2: P1 is corrupted: The simulator plays the role of P0 and the interaction with P1 is similar for the symmetric tree building of ΠOTSA GBDT , except for the simulation of Lines 2– 3 in ΠOTSA GBDT as input without labels, which can be simulated as FCPSI is secure. In both cases, under the (Fargmax -, FBOIS -, FBinMatVec -, FCPSI -, Fdiv -, Fgreater -, Fmul -, Fmux -, Fsigmoid )-hybrid, and with semantically-secure RLWE-based encryption, ΠOTSA GBDT is secure in the semi-honest model.
Appendix E. Meta-Review The following meta-review was prepared by the program committee for the 2026 IEEE Symposium on Security and Privacy (S&P) as part of the review process as detailed in the call for papers.
E.1. Summary This paper studies efficient two-party computation for the task of gradient boosting decision tree training and inference. The paper assumes that the data is vertically distributed and thus alignment is required. The most interesting optimization is how the paper optimizes circuit-PSI using homomorphic encryption to reduce the cost of alignment when the payload can be large.
E.2. Scientific Contributions •
Provides a Valuable Step Forward in an Established Field
E.3. Reasons for Acceptance The paper makes a valuable step towards practical twoparty GBDT by using homomorphic encryption to reduce the communication complexity in PSI. This leads to significant savings in their experience.