System and method of analyzing encrypted data in a database in near real-time

• US 8,626,749 B1
• Filed: 04/20/2011
• Issued: 01/07/2014
• Est. Priority Date: 04/21/2010
• Status: Active Grant

• Current Assignee: Mark Reston, Stan Trepetin
• Original Assignee: Mark Reston, Stan Trepetin
• Inventors: Trepetin, Stan, Reston, Mark
• Primary Examiner(s): Bhatia, Ajay
• Assistant Examiner(s): Park, Grace
• Application Number:
  US13/090,803
• Time in Patent Office: 993 Days
• Field of Search: None
• US Class Current: 707/722
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

The present invention relates generally to a system and method of querying an anonymized database. More particularly, the invention provides a method and system for querying an anonymized database without the need to decrypt queried data while it'"'"'s processed. Even more specifically, the invention provides a method and system of anonymizing a database such that it may be queried efficiently in near real time while still retaining the ability to not decrypt requested data while it'"'"'s being processed.

Claims

1. A computer-implemented method of anonymizing a database and querying it comprising:

(a) anonymizing a database on a server computer,

(b) hosting said database on a server computer,

(c) generating a query on a client computer,

(d) encrypting the query on the client computer to form an encrypted query,

(e) transmitting the encrypted query to the server computer,

(f) operating on the encrypted query at the server computer to produce an encrypted result,

(g) returning the encrypted result to the client computer,

(h) post processing the encrypted result on the client computer, without decryption, to produce a post processed encrypted result,

(i) decrypting the post processed encrypted result at the client computer to produce a decrypted result and presenting the decrypted result to the user;

wherein anonymizing the database is accomplished by forming two or more groups within at least one table, wherein each group is associated with an anonymization key and wherein at least two of said two or more groups overlap.

2. The method of claim 1 wherein the database is anonymized by a method which works on a single database table at a time.

3. The method of claim 1 wherein the database is anonymized by a method which anonymizes all columns of a table.

4. The method of claim 1 wherein the database is anonymized by a method which combines a deterministic process with the generation of database records which contain appropriately created fake values, wherein the number of said database records is determined by constructing mutually exclusive n-element groupings for lists of elements in the original database ordered by frequency of said elements and then creating the fake rows based on the n-element groupings which create the most fake rows.

5. The method of claim 1 wherein the database is anonymized by a method wherein a mathematical function with different anonymization parameters for each numeric column and each group is used to encode each numeric value.

6. A computer-implemented method of anonymizing a database and querying it comprising the steps of:

(a) anonymizing a database on a server computer,

(b) hosting said database on a server computer,

(c) generating a query on a client computer,

(d) encrypting the query on the client computer to form an encrypted query,

(e) transmitting the encrypted query to the server computer,

(f) operating on the encrypted query at the server computer to produce an encrypted result,

(g) returning the encrypted result to the client computer,

(h) decrypting the encrypted result at the client computer to produce a decrypted result, and

(i) post processing the decrypted result at the client computer to produce a result and presenting the result to a user;

wherein anonymizing the database is accomplished by forming two or more groups within at least one table and wherein each group is associated with an anonymization key and wherein at least two of said two or more groups overlap.

7. The method of claim 6 wherein the groups comprise subsets of rows from the at least one table.

8. The method of claim 7 wherein the groups are broken into subgroups for further anonymization.

9. The method of claim 6 wherein the anonymization key comprises subkeys.

10. The method of claim 6 wherein the table comprises zero or more false rows.

11. The method of claim 6 wherein the table is divided into one or more element groups comprising elements obtained from columns or character positions within string columns.

12. The method of claim 11 wherein each element comprises false and real rows with the proviso that each element within an element group comprises the same number of total rows.

13. The method of claim 6 wherein indices are constructed over encrypted data.

14. The method of claim 6 wherein step (a) comprises:

a. transforming a numeric value monotonically using a unique set of random parameters for each group to produce a result, and

b. storing the result in place of the numeric value in the table.

15. The method of claim 6 wherein step (a) further comprises:

creating extra tables comprising joinable elements wherein the extra tables facilitate one or more JOIN operations on two or more columns from two or more original tables.

16. A computer-implemented apparatus for performing computations on encrypted data and querying encrypted data, comprising:

(1) a computer system;

(2) logic, performed by the computer system, for (a) anonymizing a database on a server computer, (b) hosting said database on a server computer, (c) generating a query on a client computer, (d) encrypting the query on the client computer to form an encrypted query, (e) transmitting the encrypted query to the server computer, (f) operating on the encrypted query at the server computer to produce an encrypted result, (g) returning the encrypted result to the client computer, (h) post processing the encrypted result on the client computer, without decryption, to produce a post processed encrypted result, (i) decrypting the post processed encrypted result at the client computer to produce a decrypted result and presenting the decrypted result to the user;

wherein anonymizing the database is accomplished by forming two or more groups within at least one table, wherein each group is associated with an anonymization key and wherein at least two of said two or more groups overlap.

17. An article of manufacture comprising a program storage device embodying instructions for a computer-implemented method for performing computations on encrypted data and querying encrypted data, the logic comprising:

(a) anonymizing a database on a server computer, (b) generating a query on a client computer, (c) encrypting the query on the client computer to form an encrypted query, (d) transmitting the encrypted query to the server computer, (e) operating on the encrypted query at the server computer to produce an encrypted result, (f) returning the encrypted result to the client computer, (g) decrypting the encrypted result at the client computer to produce a decrypted result, and (h) post processing the decrypted result at the client computer to produce a result and presenting the result to a user;

wherein anonymizing the database is accomplished by forming two or more groups within at least one table and wherein each group is associated with an anonymization key; and

wherein at least two of said two or more groups overlap.

18. A client-server database system comprising:

(a) at least one client computer,

(b) at least one server computer, and

(c) a network connecting the client computer and the server computer,

(d) wherein the server computer hosts an anonymized database, the anonymized database is operated upon by the server computer to produce an encrypted results set in response to an encrypted query from the client computer, the encrypted results set is sent from the server to the client computer, the encrypted result is post processed on the client computer, without decryption, to produce a post processed encrypted results set, and the post processed encrypted results set is decrypted by the client computer to produce a decrypted result to be presented to a user, wherein the anonymized database is anonymized by forming two or more groups within at least one table and wherein each group is associated with an anonymization key; and

wherein at least two of said two or more groups overlap.

19. The system of claim 18 wherein the groups comprise subsets of rows from the at least one table.

20. The system of claim 18 wherein the anonymization key comprises subkeys.

21. The system of claim 18 wherein the table comprises zero or more false rows.

22. The system of claim 18 wherein the table is divided into one or more element groups comprising elements obtained from columns or character positions within string columns.

23. The system of claim 22 wherein each element comprises false and real rows with the proviso that each element within an element group comprises the same number of total rows.

24. The system of claim 18 wherein indices are constructed over encrypted data.

25. The system of claim 18 wherein the anonymized database is anonymized by:

transforming a numeric value monotonically using a unique set of random parameters for each group to produce a result, and

storing the result in place of the numeric value in the table.

26. The system of claim 18 wherein the groups are broken into subgroups for further anonymization.

27. The system of claim 18 wherein the anonymized database is anonymized by:

creating extra tables comprising joinable elements wherein the extra tables facilitate one or more JOIN operations on two or more columns from two or more original tables.