Privacy-preserving location tracking for devices

• US 8,848,924 B2
• Filed: 11/24/2008
• Issued: 09/30/2014
• Est. Priority Date: 06/27/2008
• Status: Expired due to Fees

• Current Assignee: University of Washington
• Original Assignee: University of Washington
• Inventors: Kohno, Tadayoshi, Krishnamurthy, Arvind, Maganis, Gabriel, Ristenpart, Thomas
• Primary Examiner(s): VOSTAL, ONDREJ C
• Application Number:
  US12/276,829
• Publication Number:
  US 20090323972A1
• Time in Patent Office: 2,136 Days
• Field of Search: 380/284
• US Class Current: 380/284
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06F 2221/2111 Location-sensitive, e.g. geographical location, GPS
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/06 for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 9/0631 Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator
• CPC Class Codes: H04L 9/08 Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords network architectures or network communication protocols for supporting key management in a packet data network H04L63/06
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures

Abstract

A privacy-preserving device-tracking system and method to assist in the recovery of lost or stolen Internet-connected mobile devices. The function of such a system seem contradictory, since it is desirable to hide a device'"'"'s legitimately-visited locations from third-party services and other parties to achieve location privacy, while still enabling recovery of the device'"'"'s location(s) after it goes missing by tracking the device to determine its location. An exemplary embodiment uses a DHT for storing encrypted location information and other forensic information in connection with indices that are successively determined based on initial pseudorandom seed information (i.e., state) that is retained by the owner of the device. Using the seed information, the software can determine indices mapped to location information stored after the device went missing, enabling the device to be located. Numerous extensions are discussed for the basic exemplary design that increase its suitability for particular deployment environments.

Claims

1. A system for uploading and storing a plurality of information data files on a remote storage in association with a corresponding plurality of different indices, wherein each information data file includes location information that is indicative of a location of an electronic device, comprising:

(a) a location module configured to be executed on the electronic device and to determine the location information for the electronic device;

(b) a core module configured to be executed on the electronic device and to perform actions comprising;

determining a plurality of different states over time, each state including a different seed;

using a seed of a current state to determine an index associated with the current state, wherein the index identifies a storage location for a current information data file, and wherein the index does not reveal any other storage locations used for storing other information data files;

storing the current information data file on the remote storage at the storage location identified by the index; and

using the seed to determine a subsequent seed for a subsequent state; and

(c) a retrieval module configured to be executed on a different device, wherein the retrieval module is configured to perform actions comprising;

using an initial state to determine the plurality of different states determined by the core module;

using the seeds of the plurality of different states to determine a plurality of different indices; and

using indices of the plurality of different indices to retrieve information data files including information indicative of the location of the electronic device from the remote storage.

2. The system of claim 1, wherein the core module is further configured to employ the plurality of different states to determine a succession of cryptographic keys, wherein each cryptographic key that is thus determined is usable by the core module to cryptographically protect a different one of the information data files stored on the remote storage, and wherein the retrieval module is further configured to use the plurality of different states determined using the initial state to determine the cryptographic key used to cryptographically protect the desired information data file, so that the location information included in the desired information data file can be accessed.

3. The system of claim 2, wherein the cryptographic key is usable to cryptographically protect the information data file via at least one of the following functions:

(a) encrypting the information data file, so as to maintain information included therein private; and

(b) authenticating the location information included in the information data file, to ensure that the location information was actually determined by the location module and stored on the remote storage by the core module executed by the electronic device.

4. The system of claim 1, wherein the core module is configured to respond to at least one event detected in regard to use of the electronic device, by storing the current information data file on the remote storage, wherein the at least one event indicates that the electronic device is being used by a different person than has previously used the electronic device, the at least one event being selected from the group of events consisting of:

(a) a detection that data entry dynamics are different for a current user of the electronic device than for a person previously using the electronic device; and

(b) a determination that an appearance of the current user is different than that of the person who previously used the electronic device.

5. The system of claim 1, wherein the core module is further configured to use the plurality of different states to determine a succession of pseudorandom intervals between times at which the information data files are stored on the remote storage at storage locations identified by the indices.

6. The system of claim 5, wherein the retrieval module is further configured to determine each of the successive pseudorandom intervals between times at which the information data files were stored on the remote storage, to determine which of the information data files are associated with location information data stored after a given time.

7. The system of claim 2, further comprising a cache for storing location information on the electronic device between times that the information data files are stored on the remote storage, wherein the core module is further configured to use the plurality of states to determine cache states that are used to generate a succession of cryptographic cache keys for encrypting the location information temporarily stored in the cache, a new cache state being determined based on the current state each time that a information data file is stored on the remote storage, and new cache states being determined based on a previous cache state and used to generate new cache cryptographic keys, a new cache cryptographic key being generated and used for encrypting each new location information temporarily stored in the cache.

8. The system of claim 7, wherein all of the cryptographically protected location information temporarily stored in the cache is further cryptographically protected with a current cryptographic key before being stored on the remote storage.

9. The system of claim 8, wherein the retrieval module is further configured to use the initial state to determine the cryptographic cache states, to enable access of desired location information that was cryptographically protected for temporary storage in the cache before being stored on the remote storage as the desired information data file.

10. The system of claim 2, wherein the core module is further configured to use a forward-secure generator to determine the plurality of different states using the initial state, each of the succession of cryptographic keys being generated as a function of a different state in the plurality of different states, so as to prevent a current state from being used to determine any previous state, or a current cryptographic key from being used to determine any previous cryptographic key.

11. The system of claim 1, further comprising a sensor for detecting information included in the information data files, wherein the information data files each further include at least one item selected from the group of items consisting of:

(a) a network address of the electronic device;

(b) a traceroute of a communication path between the electronic device and other devices;

(c) geolocation information based on roundtrip times for a signal conveyed between the electronic device and a plurality of other devices disposed at different known locations;

(d) a location determined using global positioning satellites;

(e) information identifying any nearby wireless data devices; and

(f) forensic information produced by a sensor on the electronic device that may indicate one of a location and a context of the electronic device, wherein the forensic information includes any one or more of;

(i) an image of an environment proximate to the electronic device;

(ii) a video of the environment proximate to the electronic device; and

(iii) audio data detected proximate to the electronic device.

12. The system of claim 2, wherein the remote storage comprises a distributed hash table, and wherein the indices that correspond to the cryptographically protected information data files are used as hash keys for storing the cryptographically protected information data files in the distributed hash table.

13. The system of claim 1, further comprising an imaging device configured to capture an image of an environment proximate to the electronic device that may show a user of the electronic device, wherein the core module is further configured to include data for the image in the current information data file stored on the remote storage.

14. The system of claim 1, wherein the core module is further configured to digitally sign each information data file that is uploaded for storage with a private key that is assigned by one or more trusted third parties as part of an anonymous group signature scheme.

15. The system of claim 14, wherein the remote storage is configured to verify that each information data file uploaded by the core module is digitally signed by the private key that is part of the anonymous group signature scheme, before storing the information data file.

16. The system of claim 1, wherein the retrieval module is configured to upload one or more software commands to storage locations identified by one or more of the determined plurality of different indices on the remote storage, so that when the core module stores a current information data file on the remote storage to the storage locations identified by those indices and detects the one or more commands stored there, the core module downloads the one or more commands and executes them on the electronic device.

17. The system of claim 16, wherein the one or more commands are at least one of encrypted, and digitally signed by the retrieval module, so that the core module decrypts the one or more commands if they are encrypted, and verifies the authenticity of the one or more commands using the digital signature if the one or more commands are digitally signed, before executing the one or more commands.

18. The system of claim 1, wherein the core module is configured to encrypt the information data files using a public key before uploading them for storage on the remote storage, the retrieval module being provided with a corresponding private key by an authorized party for use in decrypting the information data files after downloading them from the remote storage, to access the information included therein.

19. A non-transitory computer-readable memory medium on which is stored machine readable instructions for carrying out a plurality of functions to store a plurality of information data files on a remote storage in association with a corresponding plurality of different indices, wherein each information data file includes location information that is indicative of a location of an electronic device on which the machine readable instructions are being executed, the plurality of functions including:

(a) determining location information indicative of a current location of the electronic device;

(b) determining a plurality of different states over time, each state including a different seed;

(c) using a seed of a current state to determine an index associated with the current state, wherein the index identifies a storage location for a current information data file, and wherein the index does not reveal any other storage locations used for storing other information data files;

(d) storing the current information data file on the remote storage at the storage location identified by the index; and

(e) using the seed to determine a subsequent seed for a subsequent state.

20. The non-transitory computer-readable memory medium of claim 19, wherein the plurality of functions further include determining a succession of cryptographic keys, wherein each cryptographic key that is thus determined is usable to cryptographically protect a different one of the information data files stored on the remote storage.

21. The non-transitory computer-readable memory medium of claim 20, wherein the cryptographic key is usable to cryptographically protect the information data file via at least one of the following functions:

(a) encrypting the information data file, so as to maintain the location information included therein private; and

(b) authenticating the location information included in the information data file, to ensure that the location information was actually determined by the location module and stored on the remote storage by the electronic device.

22. The non-transitory computer-readable memory medium of claim 19, wherein the plurality of functions further include enabling a different device to employ an initial state that was used to determine the plurality of different states, to again determine the plurality of different states, for use in determining the succession of indices that identify storage locations at which the corresponding information data files were stored on the remote storage, so that an index that identifies a storage location at which a desired information data file is stored on the remote storage can be determined, to enable retrieval of the desired information data file and access of the location information included therein.

23. The method of claim 22, further comprising:

(a) capturing an image of a user of the electronic device; and

(b) including data for the image in the current information data file that is stored on the remote storage.

24. A computer-implemented method for uploading and storing a plurality of information data files on a remote storage in association with a corresponding plurality of different indices, wherein each information data file includes location information that is indicative of a location of an electronic device, the method comprising:

(a) determining, by the electronic device, location information indicative of a current location of the electronic device;

(b) determining, by the electronic device, a plurality of different states over time, each state including a different seed;

(c) using, by the electronic device, a seed of a current state to determine an index associated with the current state, wherein the index identifies a storage location for a current information data file, and wherein the index does not reveal any other storage locations used for storing other information data files;

(d) storing, by the electronic device, the current information data file on the remote storage at the storage location identified by the index; and

(e) using, by the electronic device, the seed to determine a subsequent seed for a subsequent state.

25. The method of claim 24, further comprising determining a succession of cryptographic keys, each cryptographic key being determined as a function of a different state of the plurality of different states, and being used to cryptographically protect one of the information data files stored on the remote storage.

26. The method of claim 25, further comprising cryptographically protecting the information data files using the cryptographic keys by carrying out at least one of the following steps:

(a) encrypting the information data files, so as to maintain the location information included therein private; and

(b) authenticating the location information included in the information data files, to ensure that the location information was actually determined by the location module and was stored on the remote storage by the electronic device.

27. The method of claim 24, further comprising determining if the electronic device is being used by a different person than has previously used the electronic device, and in response, storing the current information data file on the remote storage, the step of determining if the electronic device is being used by a different person being selected from the group of steps consisting of:

(a) detecting whether data entry dynamics are different for a current user of the electronic device than for a person previously using the electronic device; and

(b) determining whether an appearance of the current user is different than that of the person who previously used the electronic device.

28. The method of claim 25, further comprising determining a succession of pseudorandom intervals between times at which the information data files are stored on the remote storage, the pseudorandom intervals based on the plurality of different states.

29. The method of claim 28, further comprising:

(a) storing location information in a cache on the electronic device, between successive times that information data files are stored on the remote storage;

(b) using each new state of the plurality of states to determine a new cache state;

(c) using the new cache state for determining a subsequent cache state, each subsequent cache state then being used to determine a next subsequent cache state in a succession of cache states; and

(d) using each of the succession of cache states for determining a corresponding cache cryptographic key used for cryptographically protecting the location information being then temporarily stored in the cache.

30. The method of claim 29, further comprising cryptographically protecting all of the location information that was cryptographically protected before being temporarily stored in the cache, with a current cryptographic key, to produce the current information data file that is stored on the remote storage.

31. The method of claim 30, further comprising:

(a) using an initial state, again determining the plurality of different states, and using the plurality of different states to determine the succession of indices, the succession of cryptographic keys, the plurality of cache states, and the succession of cache cryptographic keys;

(b) determining an index and a cryptographic key that was used to cryptographically protect a desired information data file that was stored on the remote storage;

(c) determining the cache cryptographic keys that were employed to encrypt the location information temporarily stored in the cache that was included in the desired information data file;

(d) retrieving the desired information data file from the remote storage using the determined index; and

(e) using the cryptographic key that was previously used to cryptographically protect the desired information data file and the cache cryptographic keys that were used to cryptographically protect the location information in the cache and included in the desired information data file to access the location information included in the desired information data file.

32. The method of claim 25, wherein determining the plurality of different states over time includes generating the plurality of different states using a forward-secure pseudorandom generator starting with an initial state, and wherein determining a succession of cryptographic keys includes determining each cryptographic key as a function of a different one of the plurality of states generated using the forward-secure pseudorandom generator, so as to prevent a current cryptographic key from being used to determine any previous cryptographic key, and to prevent a seed of a current state from being used to determine any previous seed of any previous state.

33. The method of claim 24, wherein determining the location information comprises at least one of the steps of:

(a) determining a network address of the electronic device;

(b) determining a traceroute of a communication path between the electronic device and other devices;

(c) determining geolocation information based on roundtrip times for a signal conveyed between the electronic device and a plurality of other devices disposed at different known locations;

(d) determining a location using global positioning satellites;

(e) determining information identifying any nearby wireless data devices; and

(f) evaluating forensic information produced by a sensor on the electronic device that may indicate a location of the electronic device, wherein the forensic information includes any one or more of;

(i) an image of an environment proximate to the electronic device;

(ii) a video of the environment proximate to the electronic device; and

(iii) audio data detected proximate to the electronic device.

34. The method of claim 24, wherein storing the information data files includes using a distributed hash table remote storage service.

35. The method of claim 24, further comprising digitally signing each information data file that is uploaded for storage with a private key that is assigned by one or more trusted third parties as part of an anonymous group signature scheme.

36. The method of claim 35, further comprising verifying that each information data file uploaded for storage on the remote storage is digitally signed by the private key that is part of the anonymous group signature scheme before enabling the information data file to be stored on the remote storage.

37. The method of claim 24, further comprising:

(a) enabling a party that is authorized to retrieve information data files from the remote storage to determine a set of storage indices that will be used by the electronic device;

(b) uploading one or more software commands to storage locations identified by the indices on the remote storage;

(c) when the electronic device uploads an information data file to the remote storage at one of the storage locations identified by the indices, detecting the one or more commands stored there; and

(d) downloading and executing the one or more commands on the electronic device.

38. The method of claim 37, wherein the one or more commands are at least one of encrypted and digitally signed by the retrieval module, and wherein the method further comprises:

decrypting the one or more commands on the electronic device if the one or more commands are encrypted;

verifying an authenticity of the one or more commands using the digital signature if the one or more commands are digitally signed; and

executing the one or more commands on the electronic device.

39. The method of claim 24, further comprising:

(a) encrypting the information data files before uploading them for storage on the remote storage using a public key; and

(b) decrypting the information data files using a corresponding private key, after downloading them from the remote storage, to access the information included in the information data files.

40. The method of claim 24, further comprising:

determining if a current location of the electronic device corresponds to a predetermined authorized location, and if so, carrying out at least one of the steps of;

(a) suppressing upload and storage of the current information data file on the remote storage; and

(b) increasing an interval between times at which successive information data files are uploaded and stored on the remote storage compared to an interval employed when the electronic device is not at an authorized location.

41. Apparatus for storing location information for the apparatus on a remote storage in connection with a succession of indices, each index in the succession of indices being associated with a different information data file, comprising:

(a) a memory in which are stored machine executable instructions;

(b) a network interface for communicating over a network;

(c) a processor in communication with the memory and the network interface, the processor configured to execute the machine executable instructions to carry out a plurality of functions, including;

(i) determining location information indicative of a current location of the electronic device;

(ii) determining a plurality of states over time, each state including a different seed, wherein the seed for each state is used to determine an index associated with the state and to determine a subsequent seed for a subsequent state, wherein the index identifies a storage location for an information data file, and wherein the index does not reveal any other storage locations used for storing other information data files; and

(iii) communicating with the remote storage using the network interface to store, for each state of the plurality of states, an information data file on the remote storage in the storage location identified by the index associated with the state, wherein the information data file includes the location information.

42. The apparatus of claim 41, wherein the functions further include determining a succession of pseudorandom intervals between times at which the processor communicates with the remote storage to store the information data files.

43. The apparatus of claim 41, wherein the functions further include using each of the plurality of states to determine a different cryptographic key, a current cryptographic key generated using a seed of a current state being used for cryptographically protecting a current information data file before said file is stored on the remote storage.

44. The apparatus of claim 43, wherein the functions further include using each cryptographic key to cryptographically protect one of the information data files by carrying out at least one of the following functions:

(a) encrypting the information data file, so as to maintain the location information included therein private; and

(b) authenticating the location information included in the information data file, to ensure that the location information was actually determined and stored on the remote storage by the apparatus.

45. The apparatus of claim 44, wherein the memory includes a cache for temporary storage of location information between times that cryptographically protected information data files are stored on the remote storage, and wherein the functions further include:

(a) using the plurality of states to determine cache states that are used to generate successive cache cryptographic keys; and

(b) using a different cache cryptographic key for encrypting the location information each time that the location information is temporarily stored in the cache.

46. The apparatus of claim 45, wherein the functions further include cryptographically protecting all of the location information currently stored in the cache with the current cryptographic key to create a current cryptographically protected information data file that is stored on the remote storage.

47. The apparatus of claim 43, wherein the functions further include using a forward-secure generator to determine the seed for each state, wherein each seed is based on a seed of an immediately prior state, so as to prevent a current state from being used to determine any previous state, and to prevent any current cryptographic key from being used to determine any other cryptographic key.

48. The apparatus of claim 41, further comprising a sensor configured to detect information included in the information data files, and wherein the functions further include determining the location information included in the information data files corresponding to at least one item selected from the group consisting of:

(a) a network address of the electronic device;

(b) a traceroute of a communication path between the electronic device and other devices;

(c) geolocation information based on roundtrip times for a signal conveyed between the electronic device and a plurality of other devices disposed at different known locations;

(d) a location determined using global positioning satellites;

(e) information identifying any nearby wireless data devices; and

(f) forensic information produced by a sensor on the electronic device that may indicate a location of the electronic device, wherein the forensic information includes any one or more of;

(i) an image of an environment proximate to the electronic device;

(ii) a video of the environment proximate to the electronic device; and

(iii) audio data detected proximate to the electronic device.

49. The apparatus of claim 41, further comprising an imaging device configured to produce an image of a user of the apparatus, wherein the functions further include including data for an image that has been captured by the imaging device with the information data stored on the remote storage for the current state.