Method and apparatus for performing distributed privacy-preserving computations on user locations

摘要

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.

主权项

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; 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, modifying the set of encrypted local-user events to further preserve the local user's privacy, which 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 of the local user; and padding the set of encrypted local-user events to include a set of random-value entries; and sending the modified set of encrypted local-user events to the remote device.