Methods and systems for auto-completion of anonymized strings

• US 10,531,286 B2
• Filed: 10/24/2016
• Issued: 01/07/2020
• 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
• Primary Examiner(s): Nguyen, Thu Ha T
• Application Number:
  US15/332,853
• Publication Number:
  US 20180115625A1
• Time in Patent Office: 1,170 Days
• Field of Search: 709203, 709228, 709227, 709229
• 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, the proxy server performing;

receiving, from the client device, a partial query entered at the client device, wherein the partial query includes a first substring of a full query to be generated by an autocomplete suggestion;

generating a first anonymized partial query by replacing the first substring with a first anonymized string, wherein the first anonymized string is correlated with the first substring;

forwarding the first anonymized partial query to the web server;

receiving, from the web server, in response to the first anonymized partial query, a second anonymized query stored by the web server in association with the first anonymized partial query, the second anonymized query corresponding to the autocomplete suggestion;

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

sending, to the client device, the autocomplete suggestion including the first de-anonymized query, to generate the full query.

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

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

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

receiving from the web server, in response to the second anonymized query, one or more data items of a user account related to the second anonymized query; 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 partial query from the client device, wherein the second substring includes the first substring;

generating a third anonymized partial query by replacing the second substring with a third anonymized string, wherein the third anonymized string is correlated with the second substring;

forwarding the third anonymized partial query to the web server;

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

translating the fourth anonymized query into a second de-anonymized query, wherein the second de-anonymized query is correlated with the fourth anonymized query; and

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

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

after forwarding the first anonymized partial query to the web server;

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

translating the plurality of anonymized queries into respective de-anonymized queries including the first de-anonymized query, wherein the first substring is a substring of each de-anonymized query; and

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

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

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 partial queries from the second full query, wherein the partial queries include respective substrings;

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

sending the respective anonymized queries to the web server.

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

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

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 queries are tokenized queries.

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 query into the first de-anonymized query comprises decrypting the second anonymized query 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 a 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, the proxy server performing;

receiving, from the client device, a partial query entered at the client device, wherein the partial query includes a first substring of a full query to be generated by an autocomplete suggestion;

generating a first anonymized partial query by 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 queries stored at the proxy server in association with the first anonymized string;

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

forwarding the one or more de-anonymized queries 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 query from the one or more autocomplete suggestions;

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

sending the second anonymized query to the web server; and

in response to sending the second anonymized query to the web server, receiving, from the web server, one or more data items of a user account related to the second anonymized query; 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 partial queries from the second full query, wherein the partial queries include respective substrings;

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

storing the respective anonymized queries at the proxy server.

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

17. The method of claim 15, wherein storing the respective anonymized queries at the proxy server comprises storing the respective anonymized queries for the respective substrings in association with the respective anonymized query 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 that execute at the proxy server for performing:

receiving, from a client device, a partial query entered at the client device, wherein the partial query includes a first substring of a full query to be generated by an autocomplete suggestion;

generating a first anonymized partial query by replacing the first substring with a first anonymized string, wherein the first anonymized string is correlated with the first substring;

forwarding the first anonymized partial query to a web server;

receiving, from the web server, in response to the first anonymized partial query, a second anonymized query stored by the web server in association with the first anonymized partial query, the second anonymized query corresponding to the autocomplete suggestion;

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

sending, to the client device, the autocomplete suggestion including the first de-anonymized query, to generate the full query.