Abstract:
We consider the scenario of two parties having private databases that wish
to cooperate by computing a data mining algorithm on the union of their
databases. The privacy requirement means that any information learned by
a party during the computation could be learned from this party’s input
and output.
Cryptographic research has shown that for any function, the above problem
has a polynomial-time protocol. However, this solution is based on generic
constructions that involve constructing a circuit computing the algorithm
on the inputs. In this case, where the input consists of huge databases,
this type of a solution is clearly impractical.
We show that efficient solutions are possible for large databases. This
is demonstrated for the decision-tree learning algorithm ID3. Our techniques
are based on doing most of the computation locally, and reducing the problem
to a secure computation of the logarithm function. The resulting complexity
is only logarithmic in the number of items in the database (multiplied by
some other parameters), and the number of communication rounds is equal
to the decision tree depth.
Joint work with Yehuda Lindell. |
