TY - GEN

T1 - Secure multi-party computational geometry

AU - Atallah, Mikhail J.

AU - Du, Wenliang

PY - 2001

Y1 - 2001

N2 - 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. As Goldreich has recently pointed out [6], using the solutions derived from these general results to solve specific problems can be impractical; problem-specific solutions should be developed, for efficiency reasons. This paper is a first step in this direction for the area of computational geometry. We give simple solutions to some specific geometric problems, and in doing so we develop some building blocks that we believe will be useful in the solution of other geometric and combinatorial problems as well.

AB - 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. As Goldreich has recently pointed out [6], using the solutions derived from these general results to solve specific problems can be impractical; problem-specific solutions should be developed, for efficiency reasons. This paper is a first step in this direction for the area of computational geometry. We give simple solutions to some specific geometric problems, and in doing so we develop some building blocks that we believe will be useful in the solution of other geometric and combinatorial problems as well.

UR - http://www.scopus.com/inward/record.url?scp=84958035648&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958035648&partnerID=8YFLogxK

U2 - 10.1007/3-540-44634-6_16

DO - 10.1007/3-540-44634-6_16

M3 - Conference contribution

AN - SCOPUS:84958035648

SN - 3540424237

SN - 9783540424239

VL - 2125

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 165

EP - 179

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer Verlag

T2 - 7th International Workshop on Algorithms and Data Structures, WADS 2001

Y2 - 8 August 2001 through 10 August 2001

ER -