Publication details
Privacy-Preserving Distance Computation and Proximity Testing on Earth, Done Right
| Authors | |
|---|---|
| Year of publication | 2014 |
| Type | Article in Proceedings |
| Conference | Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security |
| MU Faculty or unit | |
| Citation | |
| Web | http://dl.acm.org/citation.cfm?doid=2590296.2590307 |
| Doi | http://dx.doi.org/10.1145/2590296.2590307 |
| Field | Informatics |
| Keywords | secuee multiparty computation; homomorphic encryption; privacy-preserving distance computation |
| Attached files | |
| Description | In recent years, the availability of GPS-enabled smartphones have made location-based services extremely popular. A multitude of applications rely on location information to provide a wide range of services. Location information is, however, extremely sensitive and can be easily abused. In this paper, we introduce the first protocols for secure computation of distance and for proximity testing over a sphere. Our secure distance protocols allow two parties, Alice and Bob, to determine their mutual distance without disclosing any additional information about their location. Through our secure proximity testing protocols, Alice only learns if Bob is in close proximity, i.e., within some arbitrary distance. Our techniques rely on three different representations of Earth, which provide different trade-os between accuracy and performance. We show, via experiments on a prototype implementation, that our protocols are practical on resource- constrained smartphone devices. Our distance computation protocols runs, in fact, in 54 to 78 ms on a commodity Android smartphone. Similarly, our proximity tests require between 1.2 s and 2.8 s on the same platform. The imprecision introduced by our protocols is very small, i.e., between 0.1% and 3% on average, depending on the distance. |