|
||||||
|
||||||
| Undergraduate Honours Projects | ||||||
|
Carleton University - School of Computer Science Undergraduate Honours Project Winter 2010 Select topics from Private Computation and Private Computational Geometry Simardeep Ahuja 
ABSTRACT 1.0 Abstract This focus of this paper is the study of the following problems: 1.1 The Millionaireâs Problem The discussion will be based on the protocol presented by Dr. Andrew C Yao in his research paper Protocols for Secure Computation. In his research paper, mathematical operations are used without detailed explanation of the purpose they serve. First: I present some real world analogies that fill that gap. The analogies can be used by someone unfamiliar with Mathematics and Algorithms 1) to understand the most important concepts in the protocol. Second: the fundamental idea at the heart of Yaoâs protocol is to hide information about variables i or j in the indices/ positions of numbers in a sequence. While this idea is extremely elegant, there are certain technical errors in the paper which will be discussed and solutions proposed to remedy them if possible. 1.2 Private Computation of Joint Convex Hull The discussion is based on the algorithm Privacy Preserving Convex Hull Protocol presented in the research paper On Privacy Preserving Convex Hull by Sandeep Hans et al. The algorithm presented in the aforementioned research paper is very elegant and some of the subtle points will be presented in this paper. This algorithm uses Yaoâs Protocol as a service. However, there are some lacunae in the usage of Yaoâs protocol. Suggestions on usage of Yaoâs protocol and some minor technical errors are also mentioned. 1.3 Private Computation of Nearest Pair of Points Two parties have a set of points each and wish to determine among all pairs of points which consist of one point from either partyâs set, the one with minimum separation between the two points. Ideally, this would be done in a way that neither party knows any of the points in the other partyâs set except the one that is a part of the nearest pair. At the time of writing this paper, this is an unsolved problem. A new heuristic approach is presented that strives to minimize the need to share points, while trying to generate a pair of points with separation close to the separation of the nearest pair. The approach presented only work if the points are disjoint i.e. a (any) line can be drawn such that one partyâs points are on one side of the line and the other partyâs points are on the other side. |
||||||
|
