Location brokering for providing security, privacy and services

• US 8,693,689 B2
• Filed: 11/01/2010
• Issued: 04/08/2014
• Est. Priority Date: 11/01/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Belenkiy, Mira, Morales, Henry Nelson Jerez, Roeder, Thomas Michael, Dyor, Matt
• Primary Examiner(s): Louie, Oscar
• Assistant Examiner(s): Naji, Younes
• Application Number:
  US12/917,452
• Publication Number:
  US 20120106738A1
• Time in Patent Office: 1,254 Days
• Field of Search: None
• US Class Current: 380/270
• CPC Class Codes: H04L 2209/80 Wireless
• CPC Class Codes: H04L 9/0872 using geo-location information, e.g. location data, time, relative position or proximity to other entities
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms
• CPC Class Codes: H04W 12/08 Access security

Abstract

Location brokering technique embodiments are presented that employ sensor data captured by a user'"'"'s mobile device to determine the device'"'"'s location, encrypt the location data and store it in a database. The location data is encrypted in such a way that it is possible to determine when a user'"'"'s mobile device is currently in the same vicinity as another user'"'"'s mobile device who is a member of the same group. However, the actual location and relative mobility or immobility of the users cannot be ascertained except by the users themselves via a decryption procedure or by trusted components. Services are provided can read the stored encrypted location data, processes it to determine if group members are in the same vicinity, and either respond to user queries about the location of other members of a group the user belongs to, or push this information to appropriate users.

Claims

1. A computer-implemented process for location brokering, comprising:

using one or more computers to perform the following process actions;

encrypting location data associated with multiple communication-enabled devices, wherein for each communication-enabled device associated with a user in each group of three or more communication-enabled device users,

said location data encryption comprises encrypting grid coordinates of a grid cell of a location grid in which the location of the communication-enabled device falls, but not the location within the grid cell, via an encryption scheme using a group encryption key and an initialization vector associated with the group, wherein the initialization vector associated with a group is computed based on a secret shared between the communication-enabled device users of the group and a current time interval such that the initialization vector computed by members of a group within the same time interval matches, but varies from one time interval to the next and so the encrypted location data for communication-enabled devices associated with users in the same group and located in the same grid cell within the same time interval match, and

said location data encryption further comprises,

receiving information from the communication-enabled device, wherein said information comprises,

a user identifier associated with a user of the communication-enabled device,

location data concerning the location of the communication-enabled device, and

an initialization vector for each group of users that the user of the communication-enabled device is a member of,

identifying grid coordinates of a grid cell in which the communication-enabled device'"'"'s location falls,

ascertaining the current time associated with the establishment of the received information and a current time interval in which the ascertained current time falls, and

for each group the user belongs to,

obtaining an encryption key associated with the group,

encrypting the identified grid coordinates for the group via an encryption scheme using the encryption key and initialization vector associated with the group,

encrypting a location message for the group comprising at least an encryption of the location of the communication-enabled device,

generating a location tuple, said location tuple comprising the encrypted grid coordinates for the group and the encrypted location message for the group, and

storing the location tuple generated for the group in a location database; and

providing at least one location service that gives users location-related information based on the encrypted location data, comprising,

receiving a query from a communication-enabled device associated with a querying user which asks for the location of each communication-enabled device associated with other users who belong to a group that the querying user also belongs to and who are currently located in the same grid cell as the querying user,

obtaining encrypted grid coordinates associated with the current location of the querying user,

finding location tuples in the location database that include encrypted grid coordinates that match the querying user'"'"'s encrypted grid coordinates and designating each location tuple discovered to be a matching location tuple,

for each matching location tuple, generating a neighbor tuple comprising the encrypted location message associated with the matching location tuple, and

sending the generated neighbor tuple or tuples, if any, to the communication-enabled device associated with a querying user.

2. A computer-implemented process for location brokering, comprising:

using one or more computers to perform the following process actions;

encrypting location data associated with multiple communication-enabled devices, wherein for each communication-enabled device associated with a user in each group of three or more communication-enabled device users,

said location data encryption comprises encrypting grid coordinates of a grid cell of a location grid in which the location of the communication-enabled device falls, but not the location within the grid cell, via an encryption scheme using a group encryption key and an initialization vector associated with the group, wherein the initialization vector associated with a group is computed based on a secret shared between the communication-enabled device users of the group and a current time interval such that the initialization vector computed by members of a group within the same time interval matches, but varies from one time interval to the next and so the encrypted location data for communication-enabled devices associated with users in the same group and located in the same grid cell within the same time interval match, and

said location data encryption further comprises,

receiving information from the communication-enabled device, wherein said information comprises,

a user identifier associated with a user of the communication-enabled device,

location data concerning the location of the communication-enabled device, and

an initialization vector for each group of users that the user of the communication-enabled device is a member of,

identifying grid coordinates of a grid cell in which the communication-enabled device'"'"'s location falls,

ascertaining the current time associated with the establishment of the received information and a current time interval in which the ascertained current time falls,

identifying grid coordinates of adjacent grid cells surrounding the grid cell in which the communication-enabled device'"'"'s location falls,

for each group the user belongs to,

obtaining an encryption key associated with the group,

encrypting the identified grid coordinates for the group via an encryption scheme using the encryption key and initialization vector associated with the group,

encrypting a location message for the group comprising at least an encryption of the location of the communication-enabled device,

encrypting the identified grid coordinates of each adjacent grid cell surrounding the grid cell in which the communication-enabled device'"'"'s location falls for the group via the encryption scheme using the group encryption key and initialization vector associated with the group,

generating a location tuple, said location tuple comprising the encrypted grid coordinates for the group, and the encrypted location message for the group, and the encrypted grid coordinates for the group of each adjacent grid cell surrounding the grid cell in which the communication-enabled device'"'"'s location falls, and

storing the location tuple generated for the group in a location database; and

providing at least one location service that gives users location-related information based on the encrypted location data.

3. The process of claim 2, wherein the process action of providing at least one location service that gives users location-related information based on the encrypted location data, comprises the process actions of:

receiving a query from a communication-enabled device associated with a querying user which asks for the location of each communication-enabled device associated with other users who belong to one or more of the groups that the querying user also belong to and who are currently located in the vicinity of the querying user, wherein the vicinity of the querying user comprises the grid cell in which the location of the communication-enabled device in the possession of a querying user falls and adjacent grid cells surrounding the grid cell in which the location of the communication-enabled device in the possession of a querying user falls;

obtaining encrypted grid coordinates associated with the current location of the querying user and those of adjacent grid cells surrounding the grid cell in which the current location of the querying user falls;

finding location tuples in the location database that include encrypted grid coordinates which match any of the obtained encrypted grid coordinates and designating each location tuple discovered to be a matching location tuple;

for each matching location tuple, generating a neighbor tuple comprising the encrypted location message associated with the matching location tuple; and

sending the generated neighbor tuple or tuples, if any, to the communication-enabled device associated with the querying user.

4. The process of claim 2, wherein the location tuple further comprises a user identifier associated with a user of the communication-enabled device and the time interval in which the ascertained current time fell, and wherein the process action of providing at least one location service that gives users location-related information based on the encrypted location data, comprises the process actions of:

periodically scanning the location database to identify pairs of location tuples that have a time interval which corresponds to a current time interval and wherein the encrypted grid coordinates of a first tuple of the tuple pair corresponding to the grid cell where the associated communication-enabled device is located is the same as at least one of the encrypted grid coordinates of the second tuple of the tuple pair; and

whenever at least one location tuple pair is identified, for each identified tuple pair,

generating a first neighbor tuple comprising the encrypted location message associated with a first location tuple of the identified tuple pair under consideration,

sending the first neighbor tuple to the communication-enabled device associated with the user identifier found in the second location tuple of the identified tuple pair under consideration,

generating a second neighbor tuple comprising the encrypted location message associated with the second location tuple of the identified tuple pair under consideration, and

sending the second neighbor tuple to the communication-enabled device associated with the user identifier found in the first location tuple of the identified tuple pair under consideration.

5. A computer-implemented process for location brokering, comprising:

using one or more computers to perform the following process actions;

encrypting location data associated with multiple communication-enabled devices, wherein for each communication-enabled device associated with a user in each group of three or more communication-enabled device users,

said location data encryption comprises encrypting grid coordinates of a grid cell of a location grid in which the location of the communication-enabled device falls, but not the location within the grid cell, via an encryption scheme using a group encryption key and an initialization vector associated with the group, wherein the initialization vector associated with a group is computed based on a secret shared between the communication-enabled device users of the group and a current time interval such that the initialization vector computed by members of a group within the same time interval matches, but varies from one time interval to the next and so the encrypted location data for communication-enabled devices associated with users in the same group and located in the same grid cell within the same time interval match, and

said location data encryption further comprises,

receiving information from the communication-enabled device, wherein said information comprises,

a user identifier associated with a user of the communication-enabled device,

location data concerning the location of the communication-enabled device, and

an initialization vector for each group of users that the user of the communication-enabled device is a member of,

identifying grid coordinates of a grid cell in which the communication-enabled device'"'"'s location falls,

ascertaining the current time associated with the establishment of the received information and a current time interval in which the ascertained current time falls, and

for each group the user belongs to,

obtaining an encryption key associated with the group,

encrypting the identified grid coordinates for the group via an encryption scheme using the encryption key and initialization vector associated with the group,

encrypting a location message for the group comprising at least an encryption of the location of the communication-enabled device,

generating a location tuple, said location tuple comprising the encrypted grid coordinates for the group and the encrypted location message for the group, and

storing the location tuple generated for the group in a location database; and

providing at least one location service that gives users location-related information based on the encrypted location data, wherein the location tuple further comprises a user identifier associated with a user of the communication-enabled device and the time interval in which the ascertained current time fell, and wherein providing at least one location service that gives users location-related information based on the encrypted location data, comprises;

periodically scanning the location database to identify pairs of location tuples having the same encrypted grid coordinates and a time interval that correspond to a current time interval, and

whenever at least one location tuple pair is identified, for each identified tuple pair,

generating a first neighbor tuple comprising the encrypted location message associated with a first location tuple of the identified tuple pair under consideration,

sending the first neighbor tuple to the communication-enabled device associated with the user identifier found in the second location tuple of the identified tuple pair under consideration,

generating a second neighbor tuple comprising the encrypted location message associated with the second location tuple of the identified tuple pair under consideration, and

sending the second neighbor tuple to the communication-enabled device associated with the user identifier found in the first location tuple of the identified tuple pair under consideration.