Methods and Systems for Auto-Completion of Anonymized Strings

• US 20180115625A1
• Filed: 10/24/2016
• Published: 04/26/2018
• Est. Priority Date: 10/24/2016
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Livneh, Amir
• Granted Patent: US 10,531,286 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: H04L 63/0281 Proxies
• 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/142 Managing session states for stateless protocols; Signalling session states; State transitions; Keeping-state mechanisms
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04W 12/02 Protecting privacy or anonymity, e.g. protecting personally identifiable information [PII]

Abstract

A proxy server receives, from a client device, a partial query entered at the client device. The partial query includes a first substring of a full query. The first substring is replaced with a first anonymized string that is correlated with the first substring. The first anonymized string is forwarded to a web server. A second anonymized string stored by the web server in association with the first anonymized string is received from the web server in response to the first anonymized string. The second anonymized string is translated into a first de-anonymized string that is correlated with the second anonymized string. A first autocomplete suggestion including the first de-anonymized string is sent to the client device.

Claims

1. A method, comprising:

at a proxy server having one or more processors and memory storing instructions for execution by the one or more processors, wherein the proxy server is coupled to a client device and a web server;

receiving, from the client device, a partial query entered at the client device, wherein the partial query includes a first sub string of a full query;

replacing the first substring with a first anonymized string, wherein the first anonymized string is correlated with the first substring;

forwarding the first anonymized string to the web server;

receiving, from the web server, in response to the first anonymized string, a second anonymized string stored by the web server in association with the first anonymized string;

translating the second anonymized string into a first de-anonymized string, wherein the first de-anonymized string is correlated with the second anonymized string; and

sending, to the client device, a first autocomplete suggestion including the first de-anonymized string.

2. The method of claim 1, further comprising, at the proxy server:

receiving an indication of selection of the first autocomplete suggestion from the client device;

in response to the indication, forwarding the second anonymized string as a query to the web server;

receiving from the web server, in response to the second anonymized string, one or more data items of a user account related to the second anonymized string; and

providing the one or more data items to the client device.

3. The method of claim 1, further comprising, at the proxy server:

receiving a second substring of the full query from the client device, wherein the second sub string includes the first sub string;

replacing the second substring with a third anonymized string, wherein the third anonymized string is correlated with the second substring;

forwarding the third anonymized string to the web server;

receiving, from the web server, in response to the third anonymized string, a fourth anonymized string stored by the web server in association with the third anonymized string;

translating the fourth anonymized string to a second de-anonymized string, wherein the second de-anonymized string is correlated with the fourth anonymized string; and

sending, to the client device, a second autocomplete suggestion including the second de-anonymized string.

4. The method of claim 1, further comprising, at the proxy server:

after forwarding the first anonymized string to the web server;

receiving, from the web server, a plurality of anonymized strings stored by the web server in association with the first anonymized string, wherein the plurality of anonymized strings includes the second anonymized string;

translating the plurality of anonymized strings into respective de-anonymized strings including the first de-anonymized string, wherein the first sub string is a sub string of each de-anonymized string; and

sending one or more of the de-anonymized strings to the client device as autocomplete suggestions.

5. The method of claim 1, further comprising, at the proxy server, indexing the de-anonymized strings.

6. The method of claim 1, wherein the full query is a first full query, the method further comprising, at the proxy server:

receiving a second full query;

generating multiple substrings of the second full query;

anonymizing the multiple substrings and a full string for the second full query to obtain respective anonymized strings, wherein the multiple substrings and the full string for the second full query are correlated with their respective anonymized strings; and

sending the respective anonymized strings to the web server.

7. The method of claim 6, further comprising, at the proxy server, storing the anonymized strings in respective association with the multiple substrings and the full string for the second full query.

8. The method of claim 1, wherein the first sub string is a prefix of the first de-anonymized string.

9. The method of claim 1, wherein the full query is related to personally identifiable information (PII) associated with a user account.

10. The method of claim 1, wherein the first and the second anonymized strings are tokenized strings.

11. The method of claim 1, wherein:

replacing the first substring with the first anonymized string comprises encrypting the first substring using a key that is not available to the web server; and

translating the second anonymized string into the first de-anonymized string comprises decrypting the second anonymized string using the key.

12. The method of claim 1, wherein:

the proxy server and the client device are located in a first geographic region; and

the web server and the first database are located in a second geographic region.

13. A method, comprising:

at a proxy server having one or more processors and memory storing instructions for execution by the one or more processors, wherein the proxy server is coupled to a client device and a web server;

receiving, from the client device, a partial query entered at the client device, wherein the partial query includes a first substring of the full query;

replacing the first substring with a first anonymized string, wherein the first anonymized string is correlated with the first substring;

identifying one or more anonymized strings stored at the proxy server in association with the first anonymized string;

translating the one or more anonymized strings into one or more respective de-anonymized strings, wherein the first substring is a substring of each of the de-anonymized strings; and

forwarding the one or more de-anonymized strings to the client device as one or more autocomplete suggestions.

14. The method of claim 13, further comprising, at the proxy server:

receiving, from the client device, an indication of selection of a first de-anonymized string from the one or more autocomplete suggestions;

in response to the indication, replacing the first de-anonymized string with a second anonymized string, wherein the second anonymized string is correlated with the first de-anonymized string;

sending the second anonymized string to the web server; and

in response to sending the second anonymized string to the web server, receiving from the web server one or more data items of a user account related to the second anonymized string; and

providing the one or more data items to the client device.

15. The method of claim 13, wherein the full query is a first full query, the method further comprising:

receiving a second full query;

generating multiple substrings of the second full query;

anonymizing the multiple substrings and a full string for the first full query to obtain respective anonymized strings, wherein the multiple substrings and the full string for the second full query are correlated with their respective anonymized strings; and

storing the respective anonymized strings at the proxy server.

16. The method of claim 15, wherein storing the respective anonymized strings at the proxy server comprises storing the respective anonymized strings in association with each other.

17. The method of claim 15, wherein storing the respective anonymized strings at the proxy server comprises storing the respective anonymized strings for the multiple substrings in association with the respective anonymized string for the full string.

18. The method of claim 13, wherein:

the full query is related to personally identifiable information (PII) associated with a user account;

the proxy server and the client device are located in a first geographic region; and

the web server is located in a second geographic region.

19. A non-transitory computer-readable storage medium storing one or more programs for execution by one or more processors of a proxy server, the one or more programs including instructions for:

receiving, from a client device, a partial query entered at the client device, wherein the partial query includes a first sub string of a full query;

replacing the first substring with a first anonymized string, wherein the first anonymized string is correlated with the first substring;

forwarding the first anonymized string to a web server;

receiving, from the web server, in response to the first anonymized string, a second anonymized string stored by the web server in association with the first anonymized string;

translating the second anonymized string into a first de-anonymized string, wherein the first de-anonymized string is correlated with the second anonymized string; and

sending, to the client device, a first autocomplete suggestion including the first de-anonymized string.