Cloaking with footprints to provide location privacy protection in location-based services

• US 9,736,685 B2
• Filed: 12/21/2015
• Issued: 08/15/2017
• 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
• Primary Examiner(s): HO, DAO Q
• Application Number:
  US14/976,109
• Publication Number:
  US 20160105797A1
• Time in Patent Office: 603 Days
• 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

1. A non-transitory computer readable medium bearing one or more instructions for providing location-based services to a user by cloaking a location using footprints comprising:

receiving a location associated with a mobile node, wherein the location of the mobile node comprises a selection of a spatial region from the user;

receiving an anonymity level associated with the location of 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 is from a different user and said footprints comprise historical location samples stored in an accessible database and said number of footprints taken from the database; and

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

wherein computing the region comprises determining a minimal bounding circle being computed with a polynomial-time algorithm.

2. The medium of claim 1, further comprising the instruction:

adding a footprint associated with the location of the mobile node to the database.

3. The medium of claim 1, wherein the region is a circle.

4. The medium of claim 1, wherein the location is a user'"'"'s public region that the user feels comfortable that the region is reported as current location when the user is inside the region.

5. The medium of claim 1, further comprising providing location privacy protection for the mobile node.

6. A mobile device for providing location-based services to a user by cloaking an instant location using footprints, the mobile device comprising:

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

a computer associated with the mobile device for computing an anonymity level associated with the user, wherein said computer comprising a database comprising a plurality of footprints, wherein the footprints are different mobile devices'"'"' historical location samples; and

wherein said computer configured to compute a region containing the spatial region of the mobile device and a number of footprints from the database based on the anonymity level to thereby cloak when the user is within the region and to provide the region to a location-based service to thereby preserve anonymity of the mobile device; and

wherein computing the region comprises determining a minimal bounding circle being computed with a polynomial-time algorithm.