PRIVACY-PRESERVING LOCATION TRACKING FOR DEVICES

• US 20090323972A1
• Filed: 11/24/2008
• Published: 12/31/2009
• Est. Priority Date: 06/27/2008
• Status: Active Grant

• Current Assignee: University of Washington
• Original Assignee: University of Washington
• Inventors: Ristenpart, Thomas, Maganis, Gabriel, Krishnamurthy, Arvind, Kohno, Tadayoshi
• Granted Patent: US 8,848,924 B2
• Time in Patent Office: Days
• 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 that is executed on the electronic device and determines the location information for the electronic device;

(b) a core module that is executed on the electronic device and which determines a plurality of different states for the core module over time, each state being determined by the core module as a function of a previous state and being used by the core module to determine an index that will be associated with a current information data file when the current information data file is stored on the remote storage, the core module thereby storing a succession of indices and corresponding information data files on the remote storage over time; and

(c) a retrieval module that can be executed on a different device, the retrieval module using an initial state for the core module to determine the plurality of different states, so that an index that was associated with a desired information data file when the desired information data file was stored on the remote storage can be determined by the retrieval module, enabling the desired information data file to be retrieved from the remote storage, to access the location information and any other information included therein that is indicative of the location of the electronic device.

2. The system of claim 1, wherein the core module also employs the plurality of different states to determine a succession of cryptographic keys, each cryptographic key that is thus determined being used 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 also uses the plurality of different states determined as a function of 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 cryptographically protects the information data file by carrying out at least one of the following functions:

(a) encrypting the information data files, so as to maintain 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 stored on the remote storage by the core module executed by the electronic device.

4. The system of claim 1, wherein the core module responds 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 also uses the plurality of different states to determine a succession of pseudorandom intervals between times at which the information data files and indices associated with the information data files are stored on the remote storage.

6. The system of claim 5, wherein the retrieval module further determines each of the successive pseudorandom intervals between times at which the information data files were stored on the remote storage, to determine the index associated with the desired information data file as a function of the state at the time that said file was stored on the remote storage.

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 also uses 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, based on the initial state, the retrieval module also determines 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 uses a forward-secure generator to generate cryptographic keys, based on the initial state, each of the succession of cryptographic keys being generated as a function of a different state in the plurality of 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 for storing the cryptographically protected information data files in association with their corresponding indices.

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

14. The system of claim 1, wherein the core module digitally signs 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 verifies 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 determines a set of storage indices that will be used by the electronic device and uploads one or more software commands to the indices on the remote storage, so that when the core module stores a current information data file on the remote storage to 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 encrypts the information data files before uploading them for storage on the remote storage using a public key, 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 computer-readable memory medium on which are 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; and

(b) determining a plurality of different states over time, each state being determined as a function of a previous state and being used to determine an index that is associated with a current information data file when the current information data file is stored on the remote storage, a succession of indices and corresponding information data files being thereby stored on the remote storage over time, with each index being mapped to a different information data file on the remote storage.

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

21. The computer-readable memory medium of claim 20, wherein the cryptographic key cryptographically protects the information data file 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 by the location module and stored on the remote storage by the electronic device.

22. The computer-readable memory medium of claim 19, wherein the machine readable instructions further carry out the function of enabling a different device to employ an initial state that was used to generate the plurality of different states, to again generate the plurality of different states, for use in determining the succession of indices associated with the corresponding information data files that were stored on the remote storage, so that an index associated with a desired information data file 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.

34. The method of claim 22, further comprising the steps of:

(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.

23. A 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 that is storing the information data files of the remote storage, comprising the steps of:

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

(b) determining a plurality of different states over time, each state being determined as a function of a previous state and being used to determine an index that will be associated with a current information data file when the current information data file is stored on the remote storage, a succession of indices and corresponding information data files being thereby stored on the remote storage over time, so that each index is mapped to a different information data file on the remote storage, each information data file including location information for the electronic devices at different times.

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

25. The method of claim 24, wherein the cryptographic keys cryptographically protect the information data files 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.

26. The method of claim 23, further comprising the step of 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.

27. The method of claim 24, further comprising the steps of determining a succession of pseudorandom intervals between times at which the succession of indices and corresponding information data files associated with the indices are stored on the remote storage, based on the plurality of different states.

28. The method of claim 27, further comprising the steps of:

(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.

29. The method of claim 28, further comprising the step of 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.

30. The method of claim 29, further comprising the steps of:

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

(b) determining the 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; 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.

31. The method of claim 24, wherein the step of determining a succession of cryptographic keys comprises the step of generating a succession of cryptographic keys using a forward-secure pseudorandom generator using the plurality of states, starting with an initial state, each successive cryptographic key being determined by the forward-secure pseudorandom generator as a function of a different one of the plurality of states, so as to prevent a current cryptographic key from being used to determine any previous cryptographic key, and to prevent a current seed from being used to determine any previous seed.

32. The method of claim 23, wherein the step of 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.

33. The method of claim 23, wherein the step of storing the information data files comprises the step of using a distributed hash table remote storage service.

35. The method of claim 23, further comprising the step of 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 the step of 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 23, further comprising the steps of:

(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 the indices on the remote storage;

(c) when the electronic device uploads an information data file to the remote storage at those 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, further comprising the step of decrypting the one or more commands on the electronic device, if they are encrypted;

and, if the one or more commands are digitally signed, verifying an authenticity of the one or more commands using the digital signature before executing the one or more commands on the electronic device.

39. The method of claim 23, further comprising the steps of:

(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 23, further comprising the steps of:

(a) determining if the electronic device is disposed at a predetermined authorized location; and

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

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

(ii) 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 disposed 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 executing 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 being determined as a function of a previous state and being used to determine an index that will be associated with a current information data file when the current location data file is stored on the remote storage, so that a succession of indices and corresponding information data files can be stored on the remote storage over time;

(iii) at different times, communicating with the remote storage using the network interface, and storing the succession of indices and their associated information data files on the remote storage.

42. The apparatus of claim 41, wherein the machine executable instructions further cause the processor to determine a succession of pseudorandom intervals between times at which the processor communicates with the remote storage to store the information data files and the indices associated with the information data files.

43. The apparatus of claim 41, wherein the machine executable instructions further cause the processor to use each of the plurality of states to determine a different cryptographic key, a current cryptographic key generated using 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 machine executable instructions further cause the processor to use 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, the machine executable instructions further causing the processor to:

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

(b) use 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 machine executable instructions further cause the processor to cryptographically protect 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 machine executable instructions further cause the processor to implement a forward-secure generator to generate each cryptographic key, each successive state being based on 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 that detects information included in the information data files, and wherein the machine executable instructions further cause the processor to determine the 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 that can produce an image of a user of the apparatus, wherein the machine instructions further cause the processor to include 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.