Secure Multi-Party Computational Geometry

Get BibTex-formatted data

Download

PDF

Author

Mikhail J. Atallah and Wenliang Du

Tech report number

CERIAS TR 2001-48

Entry type

inproceedings

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.

Download

PDF

URL

https://www.cerias.purdue.edu/papers/archive/2001-48.ps

Booktitle

Seventh International Workshop on Algorithms and Data Structures (WADS 2001)

Institution

CERIAS, Purdue University

Key alpha

Atallah

Note

Seventh International Workshop on Algorithms and Data Structures (WADS 2001), August, 8-10, 2001, Providence, Rhode Island, USA

Publication Date

1900-01-01

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Inproceedings{ Atallah,
	title = "Secure Multi-Party Computational Geometry",
	author = "Mikhail J. Atallah and Wenliang Du",
	booktitle = "Seventh International Workshop on Algorithms and Data Structures (WADS 2001)",
	institution = "CERIAS, Purdue University",
	note = "Seventh International Workshop on Algorithms and Data Structures (WADS 2001), August, 8-10, 2001, Providence, Rhode Island, USA",
	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.",
	url = "https://www.cerias.purdue.edu/papers/archive/2001-48.ps",
}