Secure multi-party computational geometry

Mikhail J. Atallah, Wenliang Du

Research output: Chapter in Book/Report/Conference proceedingConference contribution

183 Scopus citations

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. 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.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Verlag
Pages165-179
Number of pages15
Volume2125
ISBN (Print)3540424237, 9783540424239
DOIs
StatePublished - 2001
Externally publishedYes
Event7th International Workshop on Algorithms and Data Structures, WADS 2001 - Providence, United States
Duration: Aug 8 2001Aug 10 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2125
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other7th International Workshop on Algorithms and Data Structures, WADS 2001
CountryUnited States
CityProvidence
Period8/8/018/10/01

    Fingerprint

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this

Atallah, M. J., & Du, W. (2001). Secure multi-party computational geometry. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 2125, pp. 165-179). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2125). Springer Verlag. https://doi.org/10.1007/3-540-44634-6_16