S2VDT: A Communication-Efficient Two-Party Privacy-Preserving Vertical Decision Tree via Secure Matrix Computation

We present S2VDT, a two-party secure vertical decision tree framework built on a suite of matrix-level secure operators, including matrix multiplication, the Hadamard product, reciprocal, and vector comparison. These operators, constructed from additive secret sharing and masked matrices, provide two core advantages. First, inherent parallelism: by casting Gini impurity evaluation and split selection into matrix form, all candidate splits are evaluated simultaneously within a constant number of communication rounds, eliminating the per-split sequential interactions of prior schemes. Second, composable security: each operator is proven secure under the semihonest model via the universal composability framework, and the full training protocol achieves bounded privacy guarantees without relying on homomorphic encryption or an online trusted third party. Experiments on three real-world UCI datasets show that S2VDT matches non-private accuracy with negligible model-level precision loss while reducing communication overhead by 2.5×–7.1× and peak memory consumption by 19×–68× over Pivot.