LOCATION BROKERING FOR PROVIDING SECURITY, PRIVACY AND SERVICES

• US 20120106738A1
• Filed: 11/01/2010
• Published: 05/03/2012
• 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
• Granted Patent: US 8,693,689 B2
• Time in Patent Office: Days
• 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 as the first user. 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 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 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 shared group secret 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

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

2. The process of claim 1, wherein the process action of encrypting location data, comprises the process actions of, for each communication-enabled device:

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,

storing the location tuple generated for the group in a location database.

3. The process of claim 2, wherein the location information concerning the location of the communication-enabled device comprises sensor data captured by one of more sensors of the communication-enabled device wherein said sensor data is indicative of the location of the communication-enabled device, and wherein prior to performing the process action of identifying the grid coordinates of the grid cell in which the communication-enabled device'"'"'s location falls, performing an action of computing the location of the communication-enabled device from the sensor data.

4. The process of claim 2, wherein the location information concerning the location of the communication-enabled device, comprises the location of the communication-enabled device as derived from sensor data captured by one of more sensors of the communication-enabled device.

5. The process of claim 2, wherein the initialization vector for each group that the user of the communication-enabled device belongs to is computed using a pseudorandom function applied to a group secret encrypting key shared among the members of the group and a time interval associated with the time the location data received from the communication-enabled device was established.

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

7. The process of claim 2, further comprising the process actions of:

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

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; and

wherein

the process action of generating the location tuple for the group, further comprises including 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.

8. The process of claim 7, 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.

9. 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 having the same encrypted grid coordinates and a time interval that correspond to a current time interval;

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.

10. The process of claim 7, 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.

11. The process of claim 2, wherein the location tuple further comprises a group identifier identifying the group associated with the location tuple, 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:

receiving a location information query from a communication-enabled device associated with a querying user which comprises a user identifier associated with the querying user and a request for location-related information concerning communication-enabled devices associated with other users;

identifying the current time interval;

identifying one or more location tuples in the location database that match the criteria provided in the location information query;

for each of the identified location tuples,

attempting to obtain a privacy policy statement that corresponds to the user identifier in the identified location tuple under consideration

whenever said privacy policy statement is obtained, reviewing elements therein and determining if the statement will allow the location-related information requested by the querying user to be provided to that user,

whenever it is determined that the privacy policy statement will allow the location-related information requested by the querying user to be provided to that user, generating a neighbor tuple comprising the encrypted location message associated with the identified location tuple under consideration; and

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

12. The process of claim 11, wherein the process action of receiving a location information query, comprises an action of receiving the request for location-related information concerning communication-enabled devices associated with other users in the form of one or more elements from a set of possible elements that define what the querying user is interested in discovering, wherein said set of possible elements comprises a group element that specifies a group or groups of users, a user identifier element that specifies one or more other users, a time interval element that specifies one or more time intervals either in the past or the current time interval, and a location element specifying one or more encrypted grid coordinates, and wherein whenever an element from the set of possible elements is not included in the location information query, all instances of that element are deemed to satisfy the missing element.

13. The process of claim 11, wherein the process action of attempting to obtain the privacy policy statement, comprises an action of attempting to obtain the privacy policy statement in the form of one or more elements from a set of possible elements that define what information a user associated with the privacy policy statement wants to restrict, wherein said set of possible elements comprises a group element specifying a group of users to which the user belongs wherein the privacy policy statement applies to just that group, a current time interval element specifying the time interval in which the privacy policy statement was generated, a querying user element which specifies one or more user identifiers wherein the release of location information is restricted to just the querying user associated with the specified user identifiers, a querying user group element which specifies one or more groups of users wherein the release of location information is restricted to just querying users who are a member of at least one of the specified groups, a query time interval element which specifies one or more time intervals wherein the release of location information is restricted to just the specified time intervals, a querying user encrypted grid coordinates element which specifies one or more encrypted grid coordinates wherein the release of location information is restricted to just querying users whose associated communication-enabled device is located within a grid cell corresponding to one of the specified encrypted grid coordinates, and a user encrypted grid coordinates element which specifies one or more encrypted grid coordinates wherein the release of location information is restricted to when the user associated with the privacy policy statement is located within a grid cell corresponding to one of the specified encrypted grid coordinates, and wherein whenever an element from the set of possible elements is not included in the privacy policy statement, all instances of that element are deemed to satisfy the missing element.

14. The process of claim 2, wherein the encrypted location message for a group further comprises an encryption of at least one of a user identifier associated with a user of the communication-enabled device, or a time the communication-enabled device was at the location also encrypted in the location message.

15. A computer-implemented process for obtaining location information concerning mobile computing devices each of which is associated with a user, comprising:

using a mobile computing device associated with a first user to perform the following process actions;

receiving one or more neighbor tuples from a location service, wherein each neighbor tuple comprises an encrypted location message comprising at least an encryption of the location of a communication-enabled device;

for each received neighbor tuple,

obtaining a decryption key capable of decrypting the encrypted location message of the received neighbor tuple under consideration from a set of decryption keys known to the mobile computing device associated with a first user,

decrypting the encrypted location message found in the received neighbor tuple under consideration via a decryption scheme corresponding to the encryption scheme used to encrypt the location message, using the obtained decryption key, and

outputting the location of the communication-enabled device found in the decrypted location message, and a user identifier identifying a user associated with that communication-enabled device.

16. The process of claim 15, wherein each neighbor tuple further comprises a group identifier identifying a group of users that the first user is a member of, and wherein the process action of obtaining a decryption key capable of decrypting the encrypted location message of the received neighbor tuple under consideration from a set of decryption keys known to the mobile computing device associated with a first user, comprises an action of obtaining a group decryption key associated with the group identifier found in the neighbor tuple under consideration, and wherein the process action of decrypting the encrypted location message using the obtained decryption key, comprises an action of decrypting the encrypted location message using the obtained decryption key associated with the group identifier found in the neighbor tuple under consideration.

17. The process of claim 15, wherein the encrypted location message further comprises an encryption of the user identifier identifying the user associated with the communication-enabled device whose location was found in the decrypted location message.

18. The process of claim 15, wherein the encrypted location message further comprises an encryption of the time the communication-enabled device whose location was found in the decrypted location message was at that location, and wherein the process action of outputting the location of the communication-enabled device found in the decrypted location message and a user identifier identifying a user associated with that communication-enabled device, further comprises an action of outputting the time the communication-enabled device was at the location.

19. The process of claim 15, wherein the one or more neighbor tuples received from the location service each represent the location of a mobile computing device associated with another user who is a member of a same group of users as the first user and who are currently located within a prescribed vicinity of the mobile computing device associated with the first user, and wherein the process further includes process actions for providing location information for the mobile computing device associated with the first user to a position processing module which is accessible by the location service, said process actions comprising:

(a) capturing sensor data using one of more sensors associated with the mobile computing device associated with the first user wherein said sensor data is indicative of the location of the device;

(b) ascertaining a current time interval in which the current time falls;

(c) computing an initialization vector for each group of users that the first user is a member of, wherein computing each initialization vector for a group comprises using a pseudorandom function applied to a group secret encrypting key shared among the members of the group and the current time interval;

(d) sending the captured sensor data, a username associated with the first user, and each of the computed initialization vectors to the position processing module; and

(e) repeating actions (a) through (d) at least once during each time interval.

20. A location brokering system, comprising:

a plurality of computing devices each of which is in communication with others of the computing devices, said plurality of computing devices comprising a plurality of mobile computing devices each of which is associated with a different user and at least one cloud-based computing device; and

computer program modules each of which is executed by at least one of the computing devices, said modules comprising;

a sensor data capture module which is executed by each of the mobile computing devices and which, for each mobile computing device, captures sensor data using one of more sensors associated with the mobile computing device wherein said sensor data is indicative of the location of the device,

a location computation module which computes the location of a communication-enabled device based on the sensor data captured by that device, and which, for each of the mobile computing devices, is either executed by the mobile computing device that captured the sensor data or by a cloud-based computing device which received the sensor data from the mobile computing device,

a position processing module which encrypts the location of a communication-enabled device using information provided by the mobile computing device and the location computation module that computed the mobile computing device'"'"'s location, and which, for each group of users that the user of the mobile computing device is a member of, generates a location tuple comprising a group identifier associated with the group of users, a user identifier associated with the user of the mobile computing device, a current time interval corresponding to a current time, an encryption of the grid coordinates of a grid cell in a location grid in which location of the mobile computing device falls and which encryption is different for each group of users and each time interval, and a location message comprising an encoding of the user identifier associated with the user of the mobile computing device, the encrypted location of the mobile computing device and a time when the mobile computing device was at that location and which encryption is different for each group of users, and which, for each of the mobile computing devices, is either executed by the mobile computing device or by a cloud-based computing device,

a location database module which stores location tuples and which, for each of the mobile computing devices, is either executed by the mobile computing device or by a cloud-based computing device, and

at least one service provider module, each of which provides location-related information based on the location tuples stored in the location database, and which is executed by a cloud-based computing device.