zbMATH — the first resource for mathematics

Privacy preserving data mining. (English) Zbl 0989.68506
Bellare, Mihir (ed.), Advances in cryptology - CRYPTO 2000. 20th annual international conference, Santa Barbara, CA, USA, August 20-24, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1880, 36-54 (2000).
Summary: 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.
For the entire collection see [Zbl 0944.00095].

68P15 Database theory
68P20 Information storage and retrieval of data
94A60 Cryptography
68T05 Learning and adaptive systems in artificial intelligence