Privacy preserving data querying

• US 9,202,079 B2
• Filed: 10/25/2012
• Issued: 12/01/2015
• Est. Priority Date: 10/25/2012
• Status: Active Grant

• Current Assignee: VeriSign, Inc.
• Original Assignee: VeriSign, Inc.
• Inventors: Kaliski, Burton S. Jr.
• Primary Examiner(s): LE, HUNG D
• Application Number:
  US13/660,838
• Publication Number:
  US 20140122476A1
• Time in Patent Office: 1,132 Days
• Field of Search: None
• US Class Current: 1/1
• 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 client computer request for information from a data set of a tokenized data holder, wherein the request includes a tokenized query term, wherein the tokenized query term was tokenized by a first tokenizing authority computer different from the client computer and from a computer of an owner of the tokenized data holder, and operatively coupled to the client computer and to the tokenized data holder through a network, whereby a requestor does not have access to an entirety of the data set of the tokenized data holder; and

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, whereby the owner of the tokenized data holder does not learn the query term;

wherein the tokenized terms have each been tokenized by a second tokenizing authority computer based on a tokenizing function equivalent to a tokenizing function of the first tokenizing authority, wherein the second tokenizing authority computer is different from the client computer and from a computer of an owner of the tokenized data holder.

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 first tokenizing authority computer different from a client computer and from a tokenized data holder, and operatively coupled to the client computer and to the tokenized data holder through a network, a client computer request to tokenize a first input corresponding to a first query term;

tokenizing the first input;

transmitting the tokenized first input;

receiving, at a second tokenizing authority computer, a request to tokenize a set of inputs corresponding to a set of query terms, wherein the second tokenizing authority computer is different from the client computer and from a computer of an owner of the tokenized data holder; 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 the tokenized data holder, whereby a requestor does not have access to an entirety of the data set of the tokenized data holder, and wherein the tokenized data holder is configured to;

receive a tokenized first query term corresponding to the tokenized first input, whereby the owner of the tokenized data holder does not learn the first query term; 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, whereby a requestor does not have access to an entirety of the data set of the tokenized data holder; and

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

receive a client computer input corresponding to a query term, wherein the first tokenizing authority server is different from the client computer and from a computer of an owner of the tokenized data holder server, and operatively coupled to the client computer and to the tokenized data holder server through a network;

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, wherein the tokenized terms have each been tokenized by a second tokenizing authority server based on a tokenizing function equivalent to that of the first tokenizing authority server, wherein the second tokenizing authority computer is different from the client computer and from a computer of an owner of the tokenized data holder, whereby the owner of the tokenized data holder server does not learn the query term; 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 first 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 client computer request for information from a data set of a tokenized data holder, wherein the request includes at least one tokenized query term that was tokenized by a first tokenizing authority computer different from the client computer and from a computer of an owner of the tokenized data holder, and operatively coupled to the client computer and to the tokenized data holder through a network, wherein the tokenized query term comprises a tokenized input associated with a query term, whereby the owner of the tokenized data holder server does not learn the 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, and wherein the tokenized terms have each been tokenized by a second tokenizing authority computer based on a tokenizing function equivalent to that of the first tokenizing authority computer, wherein the second tokenizing authority computer is different from the client computer and from a computer of an owner of the tokenized data holder, whereby a requestor does not have access to an entirety of the data set of the tokenized data holder.

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 first tokenizing authority computer, a client computer request to tokenize a first input corresponding to a first query term, wherein the first tokenizing authority computer is different from the client computer and from a computer of an owner of a tokenized data holder, and operatively coupled to the client computer and to the tokenized data holder through a network;

tokenizing the first input;

transmitting the tokenized first input;

receiving, at a second tokenizing authority computer, a request to tokenize a set of inputs corresponding to a set of query terms, wherein the second tokenizing authority is different from the client computer and from a computer of an owner of the tokenized data holder;

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 the tokenized data holder, wherein the tokenized data holder is configured to;

receive a tokenized first query term corresponding to the tokenized first input, whereby an owner of the tokenized data holder does not learn the first query term; and

determine whether the tokenized first query term is contained in the set of tokenized terms, whereby a requestor does not have access to an entirety of the data set of the tokenized data holder.