# US 2014/0372753 A1 · Method and apparatus for performing distributed privacy-preserving computations on user locations

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0372753 A1
- Document ID: US20140372753A1
- Status: Published application
- Kind: A1
- Application number: 13/921,023
- Filed: 2013-06-18
- Published: 2014-12-18
- Earliest claimed: 2013-06-18
- Assignees: Palo Alto Research Center Incorporated
- Applicants: Palo Alto Research Center Incorporated
- Inventors: Emiliano DeCristofaro; Joan Melia-Segui; Rui Zhang; Oliver Brdiczka; Ersin Uzun
- Web page: https://patentgrep.com/patent/US20140372753A1

## CPC

- G06F 21/6245: {Protecting personal data, e.g. for financial or medical purposes}
- G06F 2221/2107: File encryption
- G06F 2221/2111: Location-sensitive, e.g. geographical location, GPS
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A location-trace comparison system can perform privacy-preserving computations on locations traces for two or more users, for example, to determine a location-visit overlap for these users. During operation, the system obtains location-event descriptions for locations that a local user has visited and/or is likely to visit, such that a respective location-event description indicates a location identifier and a time-interval identifier. The system encrypts the location-event descriptions to generate a corresponding set of encrypted local-user events, and receives encrypted remote-user events from a remote device, for at least one remote user. The system compares the encrypted location events to determine an overlap between the set of encrypted local-user events and the set of encrypted remote-user events. The system then determines, from the encrypted-event overlap, location-event descriptions for locations that the local and remote users have both visited and/or are both likely to visit during the same time interval.

## Claims

### Claim 1

A computer-implemented method, comprising:
obtaining location-event descriptions for locations that a local user is likely to visit, wherein a respective location-event description indicates a location identifier and a time-interval identifier;
encrypting the location-event descriptions to generate a corresponding set of encrypted local-user events;
receiving, from a remote device, encrypted remote-user events for at least one remote user;
determining an encrypted-event overlap, which involves determining an overlap between the set of encrypted local-user events and the set of encrypted remote-user events; and
determining, from the encrypted-event overlap, one or more location-event descriptions for locations that the local and remote users are both likely to visit during the same time interval.

### Claim 2 (depends on 1)

The method of claim 1, wherein encrypting a respective location-event description, Ai, involves computing:
αi=(H(Ai)*R1e)mod N;
wherein (N,e) corresponds to a public key published by the remote device, wherein R1 corresponds to a random number R1εZN generated by the local device, and wherein H(Ai) corresponds to a hash value for event description Ai.

### Claim 3 (depends on 1)

The method of claim 1, wherein determining the encrypted-event overlap involves:
sending, to the remote device, the encrypted local-user events;
receiving a set of remote-encrypted local-user events;
comparing the remote-encrypted local-user events to the encrypted remote-user events; and
determining one or more remote-encrypted local-user events that have a matching encrypted remote-user event.

### Claim 4 (depends on 3)

The method of claim 3, wherein the remote-encrypted local-user event, γi, has the form:
γi=αid mod N=H(Ai)dR1 mod N;
wherein αi corresponds to an encrypted local-user event for an event description Ai, wherein (N,d) corresponds to a private key generated by the remote device, wherein R1 corresponds to a random number generated by the local device, and wherein H(Ai) corresponds to a hash value for the event description Ai.

### Claim 5 (depends on 4)

The method of claim 4, wherein comparing the remote-encrypted local-user events to the encrypted remote-user events involves:
adjusting the remote-encrypted local-user event for a comparison operation, by computing an adjusted value H(γi/R1); and
comparing the adjusted value to the set of encrypted remote-user events.

### Claim 6 (depends on 1)

The method of claim 1, wherein the encrypted remote-user event has the form:
βi=H(H(Bi)d mod N);
wherein (N,d) corresponds to a private key generated by the remote device, and wherein H(Bi) corresponds to a hash value for event description Bi.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
modifying the set of encrypted local-user events to further preserve the local user's privacy; and
sending the modified set of encrypted local-user events to the remote device.

### Claim 8 (depends on 7)

The method of claim 7, wherein modifying the set of encrypted local-user events involves one or more of:
removing entries associated with a restricted location identifier;
removing entries associated with a restricted time interval;
removing entries for location events the local user; and
padding the set of encrypted local-user events to include a set of random-value entries.

### Claim 9 (depends on 1)

The method of claim 1, further comprising computing aggregate statistics between the local user and the at least one remote user based on the encrypted-event overlap, wherein the aggregate statistics includes one or more of:
a sum of location events in common between the local user and the at least one remote user;
an average number of location events in common between the local user and the at least one remote user; and
a variance for a number of location events in common between the local user and the at least one remote user.

### Claim 10 (depends on 1)

The method of claim 1, further comprising generating a recommendation for the local user, based on the encrypted-event overlap.

### Claim 11

A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:
obtaining location-event descriptions for locations that a local user is likely to visit, wherein a respective location-event description indicates a location identifier and a time-interval identifier;
encrypting the location-event descriptions to generate a corresponding set of encrypted local-user events;
receiving, from a remote device, encrypted remote-user events for at least one remote user;
determining an encrypted-event overlap, which involves determining an overlap between the set of encrypted local-user events and the set of encrypted remote-user events; and
determining, from the encrypted-event overlap, one or more location-event descriptions for locations that the local and remote users are both likely to visit during the same time interval.

### Claim 12 (depends on 11)

The storage medium of claim 11, wherein encrypting a respective location-event description, Ai, involves computing:
αi=(H(Ai)*R1e)mod N;
wherein (N,e) corresponds to a public key published by the remote device, wherein R1 corresponds to a random number R1εZN generated by the local device, and wherein H(Ai) corresponds to a hash value for event description Ai.

### Claim 13 (depends on 11)

The storage medium of claim 11, wherein determining the encrypted-event overlap involves:
sending, to the remote device, the encrypted local-user events;
receiving a set of remote-encrypted local-user events;
comparing the remote-encrypted local-user events to the encrypted remote-user events; and
determining one or more remote-encrypted local-user events that have a matching encrypted remote-user event.

### Claim 14 (depends on 13)

The storage medium of claim 13, wherein the remote-encrypted local-user event, γi, has the form:
γi=αid mod N=H(Ai)dR1 mod N;
wherein αi corresponds to an encrypted local-user event for an event description Ai, wherein (N,d) corresponds to a private key generated by the remote device, wherein R1 corresponds to a random number generated by the local device, and wherein H(Ai) corresponds to a hash value for the event description Ai.

### Claim 15 (depends on 11)

The storage medium of claim 11, wherein the encrypted remote-user event has the form:
βi=H(H(Bi)d mod N);
wherein (N,d) corresponds to a private key generated by the remote device, and wherein H(Bi) corresponds to a hash value for event description Bi.

### Claim 16 (depends on 11)

The storage medium of claim 11, further comprising:
modifying the set of encrypted local-user events to further preserve the local user's privacy; and
sending the modified set of encrypted local-user events to the remote device.

### Claim 17 (depends on 16)

The storage medium of claim 16, wherein modifying the set of encrypted local-user events involves one or more of:
removing entries associated with a restricted location identifier;
removing entries associated with a restricted time interval;
removing entries for location events the local user; and
padding the set of encrypted local-user events to include a set of random-value entries.

### Claim 18

An apparatus, comprising:
an event-obtaining module to obtain location-event descriptions for locations that a local user is likely to visit, wherein a respective location-event description indicates a location identifier and a time-interval identifier;
an encryption module to encrypt the location-event descriptions to generate a corresponding set of encrypted local-user events;
a communication module to receive, from a remote device, encrypted remote-user events for at least one remote user;
a comparison module to determine an encrypted-event overlap, which involves determining an overlap between the set of encrypted local-user events and the set of encrypted remote-user events; and
an encrypted-event-analysis module to determine, from the encrypted-event overlap, one or more location-event descriptions for locations that the local and remote users are both likely to visit during the same time interval.

### Claim 19 (depends on 18)

The apparatus of claim 18, wherein while encrypting a respective location-event description, Ai, the encryption module is further configured to compute:
αi=(H(Ai)*R1e)mod N;
wherein (N,e) corresponds to a public key published by the remote device, wherein R1 corresponds to a random number R1εZN generated by the local device, and wherein H(Ai) corresponds to a hash value for event description Ai.

### Claim 20 (depends on 18)

The apparatus of claim 18, wherein while determining the encrypted-event overlap, the comparison module is further configured to:
send, to the remote device, the encrypted local-user events;
receive a set of remote-encrypted local-user events;
compare the remote-encrypted local-user events to the encrypted remote-user events; and
determine one or more remote-encrypted local-user events that have a matching encrypted remote-user event.

### Claim 21 (depends on 20)

The apparatus of claim 20, wherein the remote-encrypted local-user event, γi, has the form:
γi=αid mod N=H(Ai)dR1 mod N;
wherein αi corresponds to an encrypted local-user event for an event description Ai, wherein (N,d) corresponds to a private key generated by the remote device, wherein R1 corresponds to a random number generated by the local device, and wherein H(Ai) corresponds to a hash value for the event description Ai.

### Claim 22 (depends on 18)

The apparatus of claim 18, wherein the encrypted remote-user event has the form:
βi=H(H(Bi)d mod N);
wherein (N,d) corresponds to a private key generated by the remote device, and wherein H(Bi) corresponds to a hash value for event description Bi.

### Claim 23 (depends on 18)

The apparatus of claim 18, further comprising a privacy-preserving module to modify the set of encrypted local-user events to further preserve the local user's privacy.

### Claim 24 (depends on 23)

The apparatus of claim 23, wherein while modifying the set of encrypted local-user events, the privacy-preserving module is further configured to perform one or more of:
removing entries associated with a restricted location identifier;
removing entries associated with a restricted time interval;
removing entries for location events the local user; and
padding the set of encrypted local-user events to include a set of random-value entries.
