Secure Multi-Party Computational Geometry

Feb 13, 2002

Abstract

The general secure multi-party computation problem is when multiple parties (say, Alice and Bob) each have private data (respectively, a and b) and seek to compute some function f(a,b) without revealing to each other anything unintended (i.e., anything other than what can be inferred from knowing f(a,b)). It is well known that, in theory, the general secure multi-party computation problem is solvable using circuit evaluation protocols. While this approach is appealing in its generality, the communication complexity of the resulting protocols depend on the size of the circuit that expresses the functionality to be computed. Using the solutions derived from these general results to solve specific problems is typically quite impractical; problem-specific solutions should be developed, for efficiency reasons. We give simple solutions to some geometric problems, and in doing so we develop some building blocks that have already been useful in the solution of other combinatorial problems as well.