Privacy-preserving Location Tracking of Lost or Stolen Devices: Cryptographic Techniques and Replacing Trusted Third Parties with DHTs

Thomas Ristenpart, Gabriel Maganis, Arvind Krishnamurthy, and Tadayoshi Kohno

We tackle the problem of building privacy-preserving device-tracking systems --- or private methods to assist in the recovery of lost or stolen Internet-connected mobile devices. The main goals of such systems are seemingly contradictory: to hide the device's legitimately-visited locations from third-party services and other parties (location privacy) while simultaneously using those same services to help recover the device's location(s) after it goes missing (device-tracking). We propose a system, named Adeona, that nevertheless meets both goals. It provides strong guarantees of location privacy while preserving the ability to efficiently track missing devices. We build a version of Adeona that uses OpenDHT as the third party service, resulting in an immediately deployable system that does not rely on any single trusted third party. We describe numerous extensions for the basic design that increase Adeona's suitability for particular deployment environments.

A preliminary version of this paper will appear in USENIX Security '08.

Proceedings Version:
Proceedings version of this paper is available as a pdf.

Project web page:
The source code for our system is available at

List of Updates:
June 2008 - Put up proceedings version of paper.