PRIVACY PRESERVING DATA QUERYING

• US 20140122476A1
• Filed: 10/25/2012
• Published: 05/01/2014
• Est. Priority Date: 10/25/2012
• Status: Active Grant

• Current Assignee: VeriSign, Inc.
• Original Assignee: VeriSign, Inc.
• Inventors: Kaliski, Burton S. Jr.
• Granted Patent: US 9,202,079 B2
• Time in Patent Office: Days
• US Class Current: 707/736
• CPC Class Codes: G06F 16/24564 Applying rules; Deductive queries
• CPC Class Codes: G06F 16/2457 with adaptation to user needs
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries

Abstract

A method, system, and computer-readable memory containing instructions include employing a tokenizing authority to obtain a tokenized query term that represents a query term, using the tokenized query term to perform a lookup against a tokenized term database, determining whether the tokenized query term exists in the database. The method, system, and computer-readable memory may further include returning an encryption or decryption key corresponding to an encrypted record of information associated with the query term and corresponding to the tokenized query term.

Claims

1. A computer-implemented method for preserving privacy of a query of a data set comprising:

receiving, at a computer, a request for information from a data set, wherein the request includes a tokenized query term;

determining, via the computer, whether the tokenized query term is contained in the data set, wherein the data set comprises a store of tokenized terms;

wherein the tokenized query term corresponds to a tokenized input associated with a query term, and wherein the tokenized query term and tokenized terms have each been tokenized based on an equivalent tokenizing function.

2. The method of claim 1, wherein the input is the query term.

3. The method of claim 1, wherein the input is a pre-processed query term.

4. The method of claim 3, wherein the pre-processing includes applying a blinding function.

5. The method of claim 1, wherein the tokenized terms in the store of tokenized terms correspond to tokenized store inputs, wherein at least one tokenized store input is associated with a query term that was pre-processed prior to tokenization.

6. The method of claim 1, comprising:

returning an indication that the tokenized query term is contained in the store of tokenized terms.

7. The method of claim 1, wherein the request is a request for encrypted information associated with a query term corresponding to the tokenized query term.

8. The method of claim 7 comprising:

providing the encrypted information, wherein the encrypted information comprises an encrypted record, wherein the record was encrypted using an encryption key based on a query term associated with the record.

9. The method of claim 8, wherein the encrypted record is decrypted using a decryption key based on the query term associated with the record.

10. A computer-implemented method for preserving privacy of a query of a data set comprising:

receiving, at a computer, a request to tokenize a first input corresponding to a first query term;

tokenizing the first input;

transmitting the tokenized first input;

receiving, at the computer, a request to tokenize a set of inputs corresponding to a set of query terms; and

tokenizing the set of inputs to produce a set of tokenized inputs, wherein

a set of tokenized terms corresponding to the set of tokenized inputs is stored in a tokenized data holder, and wherein the tokenized data holder is configured to;

receive a tokenized first query term corresponding to the tokenized first input; and

determine whether the tokenized first query term is contained in the set of tokenized terms.

11. The method of claim 10, wherein the first input corresponding to the first query term includes a pre-processing of the first query term, and wherein the pre-processing includes applying a blinding function.

12. The method of claim 10, wherein the tokenized data holder is further configured to:

receive a request for encrypted information associated with the first query term.

13. The method of claim 12 wherein the tokenized data holder is further configured to:

return the encrypted information, wherein the encrypted information comprises an encrypted record, wherein the record was encrypted using an encryption key based on a query term associated with the record.

14. The method of claim 10, wherein the method comprises:

calculating a decryption key based on the first query term.

15. A system for preserving privacy of a query of a data set comprising:

a tokenized data holder server containing a store of tokenized terms; and

a tokenizing authority server, wherein the tokenizing authority server is configured to;

receive an input corresponding to a query term;

perform a tokenizing function on the input; and

transmit the tokenized input; and

wherein the tokenized data holder server is configured to;

receive a tokenized query term corresponding to the tokenized input; and

determine if the tokenized query term is contained in the store of tokenized terms.

16. The system of claim 15, wherein the input corresponding to the query term includes a pre-processing of the query term, and wherein the pre-processing includes applying a blinding function.

17. The system of claim 15, wherein the tokenized terms in the store of tokenized terms correspond to tokenized store inputs, wherein at least one tokenized store input is associated with a query term that was blinded prior to tokenization.

18. The system of claim 15, wherein the tokenized data holder server is further configured to:

return an indication that the tokenized query term is contained in the store of tokenized terms.

19. The system of claim 15, wherein the tokenized data holder server is further configured to:

receive a request for encrypted information associated with the tokenized query term.

20. The system of claim 19 wherein the tokenized data holder server is further configured to:

return the encrypted information, wherein the encrypted information comprises an encrypted record, wherein the record was encrypted using an encryption key based on a query term associated with the record.

21. The system of claim 20, wherein the tokenizing authority server is further configured to:

provide a decryption key based on the query term.

22. A computer-readable medium containing instructions, which, when executed by a processor, perform a method for preserving privacy of a query of a data set, the method comprising:

receiving, at a computer, a request for information from a data set, wherein the request includes at least one tokenized query term;

determining, via the computer, whether the at least one tokenized query term is contained in the data set, wherein the data set comprises a store of tokenized terms, wherein the tokenized query term comprises a tokenized input associated with a query term, and wherein the tokenized query term and tokenized terms have each been tokenized based on an equivalent tokenizing function.

23. A computer-readable medium containing instructions, which, when executed by a processor, perform a method for preserving privacy of a query of a data set, the method comprising:

receiving, at a computer, a request to tokenize a first input corresponding to a first query term;

tokenizing the first input;

transmitting the tokenized first input;

receiving, at the computer, a request to tokenize a set of inputs corresponding to a set of query terms;

tokenizing the set of inputs to produce a set of tokenized inputs, wherein

a set of tokenized terms corresponding to the set of tokenized inputs is stored in a tokenized data holder, wherein the tokenized data holder is configured to;

receive a tokenized first query term corresponding to the tokenized first input; and

determine whether the tokenized first query term is contained in the set of tokenized terms.