CLOAKING WITH FOOTPRINTS TO PROVIDE LOCATION PRIVACY PROTECTION IN LOCATION-BASED SERVICES

• US 20100064373A1
• Filed: 09/08/2009
• Published: 03/11/2010
• Est. Priority Date: 09/05/2008
• Status: Active Grant

• Current Assignee: Iowa State University Research Foundation Incorporated (Iowa State University)
• Original Assignee: Iowa State University Research Foundation Incorporated (Iowa State University)
• Inventors: CAI, YING, XU, GE
• Granted Patent: US 8,856,939 B2
• Time in Patent Office: Days
• US Class Current: 726/26
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: G06F 2221/2111 Location-sensitive, e.g. geographical location, GPS
• CPC Class Codes: H04L 63/0421 Anonymous communication, i.e. the party's identifiers are hidden from the other party or parties, e.g. using an anonymizer
• CPC Class Codes: H04L 63/18 using different networks or channels, e.g. using out of band channels cryptographic mechanisms or cryptographic arrangements for key distribution involving distinctive intermediate devices or communication paths H04L9/0827; cryptographic mechanisms or cryptographic arrangements for authentication using a plurality of channels H04L9/3215
• CPC Class Codes: H04W 12/02 Protecting privacy or anonymity, e.g. protecting personally identifiable information [PII]
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

A method for using a location-based service while preserving anonymity includes receiving a location associated with a mobile node, receiving an anonymity level associated with the mobile node, computing a region containing the location of the mobile node and a number of footprints based on the anonymity level, wherein each of the footprints from a different user, and providing the region to a location-based service to thereby preserve anonymity of the mobile node. A method also allow a mobile device or its user to specify the anonymity level by selecting a public region consistent with a user'"'"'s feelings towards desired privacy.

Claims

10. A method for using a location-based service while preserving anonymity, the method comprising:

determining a base trajectory associated with a mobile node, the base trajectory comprising at least two points;

determining an anonymity level, K, associated with the mobile node;

computing a K-anonymity trajectory using the base trajectory, the anonymity level, and a set of other trajectories,

providing the K-anonymity trajectory to a location-based service to thereby preserve anonymity of the mobile node.

1. A method for using a location-based service while preserving anonymity, the method comprising:

receiving a location associated with a mobile node;

receiving an anonymity level associated with the mobile node;

computing a region containing the location of the mobile node and a number of footprints based on the anonymity level, wherein each of the footprints from a different user; and

providing the region to a location-based service to thereby preserve anonymity of the mobile node.

2. The method of claim 1 wherein the region is a circle.

3. The method of claim 2 wherein the computing the region comprises determining a minimal bounding circle.

4. The method of claim 3 wherein the minimal bounding circle being computed with a polynomial-time algorithm

5. The method of claim 1 wherein the location is a current location of the mobile node.

6. The method of claim 1 wherein each of the footprints being stored in a database

7. The method of claim 6 further comprising adding a footprint associated with the location and the mobile node to the database.

8. The method of claim 1 wherein each of the footprints being a location sample at a point in time.

9. The method of claim 1 wherein the anonymity level is determined by a public region selected by a user of the mobile node.

11. The method of claim 10 wherein the set of other trajectories is a set of K-1 other user trajectories.

12. The method of claim 10 wherein the computing the K-anonymity trajectory comprises performing an exhaustive search to find the K-anonymity trajectory.

13. The method of claim 10 wherein the computing the K-anonymity trajectory comprises applying a heuristic solution to find the K-anonymity trajectory.

14. The method of claim 10 wherein the computing the K-anonymity trajectory comprises cloaking the base trajectory with one trajectory.

15. The method of claim 10 wherein the computing the K-anonymity trajectory comprises cloaking the base trajectory with a set of K-1 trajectories.

16. The method of claim 10 wherein the computing the K-anonymity trajectory comprises selecting a small set of trajectories from a database for cloaking.

17. The method of claim 10 wherein the anonymity level, K, being determined based on a spatial region specified by a user of the mobile node.

18. The method of claim 17 wherein the anonymity level, K, being determined by measuring popularity of the spatial region specified by the user of the mobile node based on footprints collected from visitors to the spatial region.

19. An apparatus for providing location-based services while preserving anonymity, the apparatus comprising an anonymity server configured for receiving a location associated with a mobile node, determining the anonymity level associated with the mobile node, computing a region containing the location of the mobile node and a number of footprints based on the anonymity level, and communicating the region to a location-based service to thereby preserve anonymity of the mobile node.

20. The apparatus of claim 19 wherein the determining the anonymity level is determined based on a spatial region specified by a user of the mobile node.

22. The method of claim 20 wherein the step of determining anonymity level is determined based on a spatial regions specified the mobile device.

17-1. The apparatus of claim 16 wherein each of the footprints being'"'"'from a different user.

18-2. The apparatus of claim 16 further comprising a footprint database operatively connected to the anonymity server for storing and accessing the footprints.

19-3. The apparatus of claim 16 wherein the region is a minimal bounding circle computed with a polynomial-time algorithm.

21. A method for providing location-based services while preserving anonymity, the method comprising:

(a) determining a base trajectory associated with a mobile device, the base trajectory comprising at least two points;

(b) determining anonymity level, K, associated with the mobile device,

(c) computing a K-anonymity trajectory using the base trajectory, the anonymity level, and a set of other trajectories, and

(d) providing the K-anonymity trajectory to a location-based service to thereby preserve anonymity of the mobile device.

23. A method for providing location based services to a user, the method comprising:

providing the user with a mobile device, the mobile device having a cellular transceiver and a global positioning system (gps) receiver and wherein the mobile device is configured to receive a selection of a spatial region from the user;

receiving a selection of the spatial region from the user;

computing an anonymity level associated with the user using a computer,

receiving a location associated with the mobile device;

computing a region containing the location of the mobile device and a number of footprints based on the anonymity level, wherein each of the footprints being from a different user; and

providing the region to a location-based service to thereby preserve anonymity of the mobile device.