In this paper we introduce the concept of privacy preserving data mining. In our model, two parties owning confidential databases
wish to run a data mining algorithm on the union of their databases, without revealing any unnecessary information. This problem
has many practical and important applications, such as in medical research with confidential patient records.
Data mining algorithms are usually complex, especially as the size of the input is measured in megabytes, if not gigabytes.
A generic secure multi-party computation solution, based on evaluation of a circuit computing the algorithm on the entire
input, is therefore of no practical use. We focus on the problem of decision tree learning and use ID3, a popular and widely
used algorithm for this problem. We present a solution that is considerably more efficient than generic solutions. It demands
very few rounds of communication and reasonable bandwidth. In our solution, each party performs by itself a computation of
the same order as computing the ID3 algorithm for its own database. The results are then combined using efficient cryptographic
protocols, whose overhead is only logarithmic in the number of transactions in the databases. We feel that our result is a
substantial contribution, demonstrating that secure multi-party computation can be made practical, even for complex problems
and large inputs.
Supported by an Eshkol grant of the Israel Ministry of Science.