Querying encrypted data in a relational database system

• US 7,500,111 B2
• Filed: 05/30/2003
• Issued: 03/03/2009
• Est. Priority Date: 05/30/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mehrotra, Sharad, Hacigumus, Vahit Hakan, Iyer, Balakrishna Raghavendra
• Primary Examiner(s): Smithers; Matthew
• Assistant Examiner(s): Fields; Courtney D
• Application Number:
  US10/449,421
• Publication Number:
  US 20040243816A1
• Time in Patent Office: 2,104 Days
• Field of Search: 713/193, 713/190, 713/189, 380/279
• US Class Current: 713/193
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

A client-server relational database system, wherein data from the client computer is encrypted by the client computer and hosted by the server computer, the encrypted data is operated upon by the server computer, using one or more operators selected from a group of operators comprising: (a) inequality logic operators, (b) aggregation operators, and (c) wildcard matching operators, to produce an intermediate results set, the intermediate results set is sent from the server computer to the client computer, and the intermediate results set is decrypted and filtered by the client computer to produce actual results. The group of operators is limited because the encrypted results set, when decrypted, includes inaccuracies therein. The client computer applies a set of correction procedures to the decrypted results set to remove the inaccuracies therein.

Claims

1. A client-server relational database system, comprising:

a client computer;

a server computer; and

a network connecting the client computer and the server computer;

wherein data from the client computer is encrypted by the client computer, the encrypted data is stored by the server computer, a query is performed against the encrypted data by the server computer to produce an encrypted intermediate results set, the encrypted intermediate results set is sent from the server computer to the client computer and the encrypted intermediate results set is decrypted and filtered by the client computer to produce unencrypred actual results for the query, such that the data is always encrypted when it is stored on or processed by the server computer and the encrypted data is never decrypted by the server computer.

4. The client-server relational database system of claim 1, 2 or 3, wherein the encrypted data is operated upon by the server computer using one or more operators selected from a group of operators comprising:

(a) inequality logic operators,

(b) aggregation operators and

(c) wildcard matching operators.

5. The client-server relational database system of claim 4, wherein the group of operators is limited because the intermediate results set, when decrypted, includes inaccuracies therein.

6. The client-server relational database system of claim 5, wherein the client computer applies a set of correction procedures to the decrypted results set to remove the inaccuracies therein.

2. A client-server relational database system, comprising:

a client computer connected to a server computer, wherein data from the client computer is encrypted by the client computer, the encrypted data is stored by the server computer, a query is performed against the encrypted data by the server computer to produce an encrypted intermediate results set, the encrypted intermediate results set is sent from the server computer to the client computer and the encrypted intermediate results set is decrypted and filtered by the client computer to produce actual results for the query, such that the data is always encrypted when it is stored on or processed by the server computer and the encrypted data is never decrypted by die server computer.

3. A client-server relational database system, comprising:

a server computer connected to a client computer, wherein data from the client computer is encrypted by the client computer, the encrypted data is stored by the server computer, a query is performed against the encrypted data by the server computer to produce an encrypted intermediate results set, the encrypted intermediate results set is sent from the server computer to the client computer and the encrypted intermediate results set is decrypted and corrected by the client computer to produce actual results for the query, such that the data is always encrypted when it is stored on or processed by the server computer and the encrypted data is never decrypted by the server computer.

7. A computer-implemented method of performing computations on encrypted data, comprising:

(a) transforming a computation formulated to be performed on unencrypted data so that at least a portion of the computation can be applied to the encrypted data;

(b) applying the transformed computation to the encrypted data on a first computer in order to obtain intermediate encrypted results;

(c) decrypting the intermediate encrypted results on a second computer; and

(d) applying at least a remaining portion of the computation to the decrypted results on the second computer in order to obtain actual results for the computation;

(e) such that the data is always encrypted when it is stored on or processed by the first computer and the encrypted data is never decrypted by the first computer.

8. The method of claim 7, wherein the inns forming step (a), decrypting step (c) and applying step (d) are performed by a client computer and the applying step (b) is performed by a server computer.

9. The method of claim 8, wherein the server computer stores the encrypted data.

10. The method of claim 8, wherein the client computer sends the transformed computation to the server computer.

11. The method of claim 8, wherein the server computer sends the intermediate encrypted results to the client computer.

12. The method of claim 8, wherein additional information is stored with the encrypted data.

13. The method of claim 12, wherein the additional information comprises one or more partition ids associated with at least one attribute of the encrypted data.

14. The method of claim 13, wherein the partition ids are created by partitioning a value domain of the attribute of the encrypted data and labeling partitions resulting therefrom.

15. The method of claim 14, wherein the partitions cover a whole of the value domain.

16. The method of claim 14, wherein the partitions do not overlap.

17. The method of claim 14, wherein the partitions do overlap.

18. The method of claim 14, further comprising partitioning at least one operation of the computation for execution across the client computer and the server computer.

19. The method of claim 18, wherein the operation comprises a selection operation, a relation referenced by the selection operation is transmitted from the server computer to the client computer, the relation is decrypted by the client computer and the selection operation is performed by the client computer on the decrypted relation.

20. The method of claim 18, wherein the operation comprises a selection operation, the selection operation is partially computed at the server computer using the partition ids associated with the attributes, the results therefrom are decrypted by the client computer and the decrypted results are filtered by the client computer to complete the selection operation.

21. The meted of claim 18, wherein the operation comprises a join operation, the join operation is partially computed at the serves computer using the partition ids associated with the attributes, the results therefrom are decrypted by the client computer and the decrypted results are filtered by the client computer to complete the join operation.

22. The method of claim 18, wherein the operation comprises a grouping and aggregation operation, the grouping operation is partially performed at the server computer using the partition ids associated with the attributes, the results therefrom are decrypted by the client computer, the grouping operation is completed on the decrypted results by the client computer and the aggregation operation is performed by the client computer on results therefrom.

23. The method of claim 18, wherein the operation comprises a sorting operation, a grouping operation is performed at the server computer using the partition ids associated with the attributes, results from the grouping operation are decrypted by the client computer and the sorting operation is completed on the decrypted results by the client computer.

24. The method of claim 18, wherein the operation comprises a duplicate elimination operation, a grouping operation is performed at the server computer using the partition ids associated with the attributes, results from the grouping operation are decrypted by the client computer and the duplicate elimination operation is completed on the decrypted results by the client computer.

25. The method of claim 18, wherein the operation comprises a set difference operation, a left outer join operation is performed at the server computer using the partition ids associated with the attributes, results from the left outer join operation are decrypted by the client computer and the set difference operation is completed on the decrypted results by the client computer.

26. The method of claim 18, wherein the operation comprises a union operation, the union join operation is performed at the server computer using the partition ids associated with the attributes, results from the left outer join operation are decrypted by the client computer and the union operation is completed on the decrypted results by the client computer.

27. The method of claim 18, wherein the operation comprises a projection operation, a relation is transmitted from the server computer to the client computer, the relation is decrypted by the client computer, and the projection operation is performed by the client computer on the decrypted relation.

28. The method of claim 18, wherein the operation comprises a projection operation, a relation is transmitted from the server computer to the client computer, the relation is decrypted by the client computer, and the projection operation is performed by the client computer on the decrypted relation.

29. The method of claim 12, wherein the additional information comprises results from one or more modulo divisions of the attribute by components of an encryption key.

30. The method of claim 29, wherein the operation comprises an aggregation operation, the aggregation operation is partially performed at the server computer using the results from the modulo divisions of the attribute by the components of the encryption key, results therefrom are decrypted by the client computer, and the aggregation operation is completed on the decrypted results by the client computer.

31. The method of claim 12, wherein the additional information comprises a bit string signature of the attribute that is computed by inclusion and exclusion of pre-selected key strings.

32. The method of claim 31, wherein the operation comprises a wildcard matching operation, the wildcard matching operation is partially performed at the server computer using the bit string signature of the attribute, results therefrom are decrypted by the client computer, and the wildcard matching operation is completed on the decrypted results by the client computer.

33. The method of claim 8, wherein the applying step (b) comprises applying the transformed computation to the encrypted data using one or more privacy homomorphisms that support arithmetic operations on the encrypted data.

34. The method of claim 33, wherein the arithmetic operations are defined in modular arithmetic and a modulo divisor n is selected such that n=p*q, where an encryption key for the encrypted data comprises k=(p,q), and results from the modular arithmetic fall in a range defined by [0,n).

35. The method of claim 34, wherein the arithmetic operations include a division operation that is supported by leaving a result in fractional form by computing a numerator and a denominator of the division separately, and then returning the numerator and a denominator to the client computer which decrypts the encrypted data and completes the division operation using the decrypted data.

36. The method of claim 34, wherein the arithmetic operations include floating point numbers that are represented as fractions.

37. The method of claim 34, wherein the arithmetic operations include negative numbers that are mapped to shifted values in a new range, and the shifted values are returned to the client computer, which decrypts the encrypted data and maps the shifted values to the negative numbers.

38. The method of claim 34, wherein random noise is added to the encrypted data, so that the arithmetic operations are prevented from testing for equality, and the random noise is removed from the encrypted data at the client computer after decryption.

39. A computer-implemented apparatus for performing computations on encrypted data, comprising:

(1) a computer system;

(2) logic, performed by the computer system, for

(a) transforming a computation formulated to be performed on unencrypted data so that at least a portion of the computation can be applied to the encrypted data;

(b) applying the transformed computation to the encrypted data on a first computer in order to obtain intermediate encrypted results;

(c) decrypting the intermediate encrypted results on a second computer; and

(d) applying at least a remaining portion of the computation to the decrypted results on the second computer in order to obtain actual results for the computation;

(e) such that the data is always encrypted when it is stored on or processed by the first computer and the encrypted data is never decrypted by the first computer.

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

(a) transforming a computation formulated to be performed on unencrypted data so that at least a portion of the computation can be applied to the encrypted data;

(b) applying the transformed computation to the encrypted data on a first computer system in order to obtain intermediate encrypted results;

(c) decrypting the intermediate encrypted results on a second computer system; and

(d) applying at least a remaining portion of the computation to the decrypted results on the second computer system in order to obtain actual results for the computation;

(e) such that the data is always encrypted when it is stored on or processed by the first computer and the encrypted data is never decrypted by the first computer.