Enhancing the Efficiency in Privacy Preserving Learning of Decision Trees in Partitioned Databases

Abstract

This paper considers a scenario where two parties having private databases wish to cooperate by computing a data mining algorithm on the union of their databases without revealing any unnecessary information. In particular, they want to apply the decision tree learning algorithm ID3 in a privacy preserving manner. Lindell and Pinkas (2002) have presented a protocol for this purpose, which enjoys a formal proof of privacy and is considerably more efficient than generic solutions.
The crucial point of their protocol is the approximation of the logarithm function by a truncated Taylor series. The present paper improves this approximation by using a suitable Chebyshev expansion. This approach results in a considerably more efficient new version of the protocol.