Learning Decision Trees Through Black-Box Queries.

摘要

We investigate the information leakage in private decision tree evaluation protocols. A private decision tree evaluation protocol is a two party computation protocol in which one party p 1 holds a private input while the other party p 2 holds a private decision tree. The aim of the protocol is to securely evaluate the private decision tree on the private input and return p1 the result. By securely evaluation, we mean that after the execution of the protocol, neither p1 should learn anything about the details of the decision tree, nor p 2 should learn about p1's input.;Moreover, we evaluate the effectiveness of the well-known decision tree learning algorithm ID3 when used to attack these protocols with the aim of learning the private decision tree. We perform this task by efficiently implementing this algorithm. We run our attack and the ID3 algorithm on many random decision trees in order to experimentally compare the accuracy and efficiency of these algorithms.;In general, these protocols guarantee the privacy of a private decision tree in a single protocol execution. Every time the protocol is run, one input/output relationship of the tree is learned. We are interested to know how many runs of a private univariate decision tree evaluation protocol is needed to learn the private tree itself. Towards answering this question, we design an efficient attack against such protocols which invokes the private decision tree evaluation protocol repeatedly and on different inputs with the aim of recovering the entire tree. In order to ensure correctness and efficiency of the proposed attack, we make some assumptions on the structure of the private univariate decision tree which we aim to learn. We implement our attack algorithm to experimentally evaluate its accuracy and efficiency when run on many random decision trees.