僦刨胸谷重.PDFVIP

Secure Multi-Party Computational Geometry Mikhail J. Atallah and Wenliang Du Department of Computer Sciences and Center for Education and Research in Information Assurance and Security Purdue University West Lafayette, IN 47907 fmja, duw g@ Abstract. The general secure multi-party computation problem is when multiple parties (say, Alice and Bob) each have private data (resp ectively, 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 b e 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 proto cols. While this approach is app ealing in its general- ity, the communication complexity of the resulting proto cols dep end on the size of the circuit that expresses the functionality to b e computed. As Goldreich has recently p ointed out [6], using the solutions derived from these general results to solve sp ecic problems can b e impractical; problem-sp ecic solutions should b e develop ed, for eÆciency reasons. This pap er is a rst step in this direction for the area of computational geometry. We give simple solutions to some sp ecic geometric problems, and in doing so we develop some building blo cks that we b elieve will b e useful in the solution of other geometric and combinatorial problems as well. 1 Intro duction The growth of the Internet op ens up tremendous opp ortunities for co o