Preserving privacy by concealing location information with a pseudo-random permutation process

• US 9,955,346 B2
• Filed: 12/05/2013
• Issued: 04/24/2018
• Est. Priority Date: 12/05/2013
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Bohli, Jens-Matthias, Karame, Ghassan, Li, Wenting, Dobre, Dan
• Primary Examiner(s): Patel, Haresh N
• Application Number:
  US15/101,491
• Publication Number:
  US 20160309322A1
• Time in Patent Office: 1,601 Days
• Field of Search: 726 26
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: H04W 12/02 Protecting privacy or anonymity, e.g. protecting personally identifiable information [PII]
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences

Abstract

A method for preserving privacy within a communication system, wherein a location-based service concerning an area of interest is provided for at least one user by a database server and wherein location information represented by coordinates of objects and/or users and/or areas and/or queries, made to the location-based service, is concealed, includes concealing the location information by transforming coordinates by first splitting the area of interest up in tiles for providing at least one tiling of the area of interest, and then permuting the tiles by a pseudo-random permutation process.

Claims

1. A method for concealing location information within a communication system including a database server configured to provide location-based services, the method comprising:

receiving, from a subscriber, a data structure directed to the database server, the data structure including coordinates pertaining to location information of the subscriber, the coordinates being located within an area of interest;

transforming the coordinates located within the area of interest and pertaining to the subscriber by;

dividing the area of interest into tiles so as to provide a tiling of the area of interest,

permuting the tiles by a pseudo-random permutation process so as to provide a permuted tiling of the area of interest, and

applying an order-preserving encryption (OPE) process to the permuted tiling of the area of interest; and

providing, to the database server, a data structure including transformed coordinates pertaining to the subscriber so as to conceal the location information of the subscriber.

2. The method according to claim 1, wherein in dividing the area of interest into tiles so as to provide a tiling of the area of interest, three different tilings are created.

3. The method according to claim 2, wherein in permuting the tiles by a pseudo-random permutation process so as to provide a permuted tiling of the area of interest, each of the three different tilings is permuted by a pseudo-random permutation process so as to provide three different permuted tilings of the area of interest, and

wherein in applying the order-preserving encryption (OPE) process to the permuted tiling of the area of interest, the order-preserving encryption process is applied to each of the three different permuted tilings separately.

4. The method according to one claim 2, wherein the three different tilings are each stored at different servers.

5. The method according to claim 1, wherein the pseudo-random permutation process comprises one or more of a rotation of the tiles, a flipping of the tiles, or a shuffling of the tiles.

6. The method according to claim 5, wherein the rotation of the tiles comprises rotating each tile individually.

7. The method according to claim 5, wherein the flipping of the tiles comprises flipping each tile individually.

8. The method according to claim 1, wherein a location privacy layer is used for a translation or transformation of the location information or coordinates.

9. The method according to claim 8, wherein the location privacy layer mediates the exchange of information between at least one of objects or users on one side and the database server on the other side.

10. The method according to claim 8, wherein the location privacy layer judges and relays a location information input from at least one of an object or user to a tiling in which a movement of an object or user does not cross a boundary of a tile.

11. The method according to one claim 1, wherein the location-based services comprises a geo-fencing application.

12. The method according to claim 1, wherein the location-based services are provided using a cloud server.

13. A communication system for concealing location information in location-based services, comprising:

a database server configured to provide a location-based service; and

a processor configured to;

receive, from a subscriber, a data structure directed to the database server, the data structure including coordinates pertaining to location information of the subscriber, the coordinates being located within an area of interest,

transform the coordinates located within the area of interest and pertaining to the subscriber by dividing the area of interest into tiles so as to provide a tiling of the area of interest, permute the tiles by a pseudo-random permutation process so as to provide a permuted tiling of the area of interest, and apply an order-preserving encryption (OPE) process to the permuted tiling of the area of interest, and

provide, to the database server, a data structure including transformed coordinates pertaining to the subscriber so as to conceal the location information of the subscriber.