Consider two or more parties who want to perform a joint computation, but neither party is willing to reveal its input. This problem is known as Secure Multiparty Computation (SMC). It deals with computing a probabilistic function in a distributed system where each participant independently holds one of the inputs, while ensuring correctness of the computation and revealing no information to a participant other than his input and output.
There exist general-purpose constructions that convert any polynomial computation to a secure multiparty computation [37]. Recent work has considerably improved the efficiency of such computations when an approximate answer is sufficient [13]. Applications include privacy-preserving data classification, clustering, generalization, summarization, characterization, and association rule mining. Clifton et al. [8] present methods for secure addition, set union, size of set intersection, and scalar product. Lindell and Pinkas [19] propose a protocol for secure decision tree induction, consisting of many invocations of smaller private computations such as oblivious function evaluation. Unfortunately, the cost of even the most efficient SMC schemes is too high for the purpose of large-scale security alert distribution.