  Federated learning (FL) is an emerging paradigm that enables multiple
organizations to jointly train a model without revealing their private data to
each other. This paper studies {\it vertical} federated learning, which tackles
the scenarios where (i) collaborating organizations own data of the same set of
users but with disjoint features, and (ii) only one organization holds the
labels. We propose Pivot, a novel solution for privacy preserving vertical
decision tree training and prediction, ensuring that no intermediate
information is disclosed other than those the clients have agreed to release
(i.e., the final tree model and the prediction output). Pivot does not rely on
any trusted third party and provides protection against a semi-honest adversary
that may compromise $m-1$ out of $m$ clients. We further identify two privacy
leakages when the trained decision tree model is released in plaintext and
propose an enhanced protocol to mitigate them. The proposed solution can also
be extended to tree ensemble models, e.g., random forest (RF) and gradient
boosting decision tree (GBDT) by treating single decision trees as building
blocks. Theoretical and experimental analysis suggest that Pivot is efficient
for the privacy achieved.
