Privacy-preserving cookies for personalization without user tracking

• US 10,108,817 B2
• Filed: 09/26/2014
• Issued: 10/23/2018
• Est. Priority Date: 09/26/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Riva, Oriana, Nath, Suman, Burger, Douglas Christopher, Mor, Nitesh
• Primary Examiner(s): Jamshidi, Ghodrat
• Application Number:
  US14/497,950
• Publication Number:
  US 20160092699A1
• Time in Patent Office: 1,488 Days
• CPC Class Codes: G06F 21/6263 during internet communication, e.g. revealing personal data from cookies
• CPC Class Codes: H04L 63/0421 Anonymous communication, i.e. the party's identifiers are hidden from the other party or parties, e.g. using an anonymizer
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/306 User profiles
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34
• CPC Class Codes: H04W 12/02 Protecting privacy or anonymity, e.g. protecting personally identifiable information [PII]

Abstract

The privacy-preserving cookie generator implementations described herein create a privacy-preserving data structure (also called a privacy-preserving cookie herein) that is used to provide personalization for online services without user tracking. In some implementations the privacy-preserving cookie generator encodes a user profile (for example, based on a user'"'"'s online activity) into a data structure that has naturally occurring noise and that efficiently supports noise addition. In one implementation a Bloom filter is used to create the encoded profile. Additional noise is injected into the encoded profile to create an obfuscated user profile in the form of a privacy-preserving data structure. The privacy-preserving data structure or cookie can be attached to an online service request and sent over a network to an online service provider which can use it fulfill the services request, providing a somewhat personalized result while the user'"'"'s privacy is maintained.

Claims

1. A computer-implemented process for creating a privacy-preserving data structure representing an obfuscated user profile to provide personalization for online services without user tracking, comprising:

encoding a user profile into a data structure that has naturally occurring noise and that efficiently supports noise addition; and

injecting noise into the encoded data structure to create the privacy-preserving data structure representing the obfuscated user profile that allows personalized online services to be provided to a user while maintaining a specified level of user privacy,

wherein the noise injected into the encoded data structure is automated to allow for a tradeoff between the specified level of user privacy and a level of personalization, and

wherein the noise injected is automated by using a personalization prediction model that computes a loss of personalization using online histories for a set of users and independently varying a number of hash functions and an amount of noise used to build the privacy-preserving structure.

2. The computer-implemented process of claim 1, further comprising:

sending the privacy preserving data structure over a network with a client request;

and

receiving service results over the network in response to the request.

3. The computer-implemented process of claim 2, wherein the privacy-preserving data structure is sent over the network with a search query;

and wherein the received services are search results.

4. The computer-implemented process of claim 1, wherein the user profile is encoded using a Bloom filter.

5. The computer-implemented process of claim 4, wherein the noise is injected by setting random bits in the encoded data structure and by controlling the probability of false positives naturally occurring in Bloom filters.

6. The computer-implemented process of claim 5, wherein an increased number of random bits that are set in the encoded data structure increases the level of user privacy.

7. The computer-implemented process of claim 5, wherein the number of bits set represents noise and wherein the level of noise is controlled by the fraction of bits set in the Bloom filter.

8. The computer-implemented process of claim 1, wherein the privacy-preserving data structure is created without the use of a noise dictionary.

9. The computer-implemented process of claim 1, wherein the user profile is based on a user'"'"'s online activities.

10. A system for preserving user privacy while providing personalized online services, comprising:

a computing device;

a computer program, stored on a memory device, comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

build a personalization profile based on a user'"'"'s online activities;

encode the personalization profile by applying a Bloom filter to the personalization profile;

inject noise into the encoded personalization profile to create a privacy-preserving cookie, wherein the injection of noise allows for a tradeoff between a specified level privacy and a level of personalization, and wherein the noise is controlled by setting a random number of bits in the encoded personalization profile; and

attach the privacy-preserving cookie to an online service request sent over a network to allow a service provider to provide personalized results in response to the request while maintaining user privacy.

11. The system of claim 10, wherein the injection of noise is automated.

12. The system of claim 10, wherein user privacy is increased by setting a greater number of random bits in the encoded personalization profile.

13. The system of claim 10, wherein communication overhead is reduced by using the privacy-preserving cookie in a search application.

14. The system of claim 10, wherein a level of obfuscation of the personalization profile is configured through the number of hash functions applied to the bits of the personalization profile when encoding the personalization profile by applying the Bloom filter.

15. The system of claim 10, wherein the noise injected into the personalization profile to create the privacy-preserving cookie is automated to allow for a tradeoff between a level of personalization and a level of privacy.

16. The system of claim 15, wherein the automation comprises:

building a personalization prediction model by computing a loss of personalization using online histories for a set of users by independently varying a number of hash functions and an amount of noise used to build the privacy-preserving cookie representing an obfuscated user profile;

building a privacy prediction model using the online histories by computing similarity of each user'"'"'s profile in the set of users over time and grouping the users'"'"' profiles into categories based on similarity values;

receiving a privacy goal and a personalization goal from a user;

computing a similarity value for the user;

comparing the similarity value for the user to the categories of users'"'"' profiles based on similarity values; and

automatically determining an amount of noise and a number of hash functions for encoding a privacy-preserving cookie representing an obfuscated user profile that meets the privacy goal and the personalization goal received from the user.

17. The system of claim 16, wherein the similarity value of each user'"'"'s profile is determined by using a Jaccard similarity function.

18. The system of claim 16, wherein the personalization goal is a maximum acceptable percentage of personalization loss obtained with an obfuscated profile compared to the personalization obtained by using the user'"'"'s unobfuscated profile.

19. The system of claim 16, wherein the privacy goal is based on minimum unlinkability.

20. A computer-implemented process for providing personalization of online services without user tracking, comprising:

receiving a user'"'"'s online service request and an obfuscated user profile created by applying a Bloom filter to an original user profile and setting random bits in the obfuscated user profile, wherein the level of obfuscation of the user profile is determined by using a privacy prediction model created by computing for a set of users over time a similarity value of each user'"'"'s profile and grouping the users'"'"' profiles into categories based on similarity values;

retrieving services in response to the user'"'"'s online service request; and

ranking the retrieved results using the obfuscated user profile to provide personalized online services to the user.