Cryptology ePrint Archive: Report 2015/386

Privately Evaluating Decision Trees and Random Forests

David J. Wu and Tony Feng and Michael Naehrig and Kristin Lauter

Abstract: Decision trees and random forests are common classifiers with widespread use. In this paper, we develop two protocols for privately evaluating decision trees and random forests. We operate in the standard two-party setting where the server holds a model (either a tree or a forest), and the client holds an input (a feature vector). At the conclusion of the protocol, the client learns only the model's output on its input and a few generic parameters concerning the model; the server learns nothing. The first protocol we develop provides security against semi-honest adversaries. Next, we show an extension of the semi-honest protocol that obtains one-sided security against malicious adversaries. We implement both protocols and show that both variants are able to process trees with several hundred decision nodes in just a few seconds and a modest amount of bandwidth. Compared to previous semi-honest protocols for private decision tree evaluation, we demonstrate tenfold improvements in computation and bandwidth.

Category / Keywords: cryptographic protocols / public-key cryptography, applications, machine learning

Date: received 24 Apr 2015

Contact author: dwu4 at cs stanford edu

Available format(s): PDF | BibTeX Citation

Version: 20150429:000115 (All versions of this report)

Short URL: ia.cr/2015/386

Discussion forum: Show discussion | Start new discussion