Securely processing range predicates on cloud databases

Patent metadata

Field	Value
Publication number	US-10055602-B2
Application number	US-201615132511-A
Country	US
Kind code	B2
Filing date	Apr 19, 2016
Priority date	Apr 19, 2016
Publication date	Aug 21, 2018
Grant date	Aug 21, 2018

Abstract

Methods, systems, and computer program products for securely processing range predicates on cloud databases are provided herein. A computer-implemented method includes separately encrypting a set of plain text data using two or more encryption functions, thereby producing an encrypted domain comprising at least two distinct groups of encrypted data items; converting a range query over plain text data items into a query over at least one of the distinct groups of encrypted data items; and combining results from the query over the distinct groups of encrypted data items, thereby generating a final encrypted result to the range query.

First claim

What is claimed is:

1. A computer-implemented method, comprising steps of:
separately encrypting a set of plain text data using two or more encryption functions, thereby producing an encrypted domain comprising at least two distinct groups of encrypted data items, wherein the two or more encryption functions comprise (i) a brute force safe function and (ii) a range safe function;
converting a range query over plain text data items into a query over at least one of the distinct groups of encrypted data items; and
combining results from the query over the distinct groups of encrypted data items, thereby generating a final encrypted result to the range query;
wherein the steps are carried out by at least one computing device.

2. The computer-implemented method of claim 1 , wherein the set of plain text data comprises a table of plain text data.

3. The computer-implemented method of claim 1 , wherein the at least two distinct groups of encrypted data items comprise at least two distinct encrypted tables.

4. The computer-implemented method of claim 1 , wherein the at least two distinct groups of encrypted data items comprise a specific number of distinct groups of encrypted data that is dependent on the number of columns in the set of plain text data.

5. The computer-implemented method of claim 1 , wherein the at least two distinct groups of encrypted data items comprise at least two ciphertexts.

6. The computer-implemented method of claim 1 , wherein the at least two distinct groups of encrypted data items comprise (i) a range safe view of encrypted data items and (ii) a brute force safe view of encrypted data items.

7. The computer-implemented method of claim 1 , wherein said separately encrypting comprises using a distinct combination of (i) prefix-preserving encryption, (ii) order-preserving encryption and/or (iii) secure block cipher to encrypt the set of plain text data.

8. The computer-implemented method of claim 1 , wherein said separately encrypting comprises using an independently generated key to encrypt the set of plain text data.

9. The computer-implemented method of claim 1 , wherein said converting comprises mapping an input range from the set of plain text data to a set of multiple sub-ranges over the encrypted domain that can be evaluated over the at least two distinct groups of encrypted data items.

10. The computer-implemented method of claim 1 , wherein said converting comprises converting the range query from the set of plain text data into (i) a range safe query and (ii) a brute force safe query.

11. The computer-implemented method of claim 1 , wherein said combining comprises performing a disjoint union operation on a set of results from the query over the least two distinct groups of encrypted data items.

12. The computer-implemented method of claim 1 , comprising:
decrypting the final encrypted result, thereby generating a plain text result set.

13. The computer-implemented method of claim 12 , comprising:
outputting the plain text result set to a client that provided the range query.

14. A computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a device to cause the device to:
separately encrypt a set of plain text data using two or more encryption functions, thereby producing an encrypted domain comprising at least two distinct groups of encrypted data items, wherein the two or more encryption functions comprise (i) a brute force safe function and (ii) a range safe function;
convert a range query over plain text data items into a query over at least one of the distinct groups of encrypted data items; and
combine results from the query over the distinct groups of encrypted data items, thereby generating a final encrypted result to the range query.

15. The computer program product of claim 14 , wherein the program instructions executable by a computing device further cause the computing device to:
decrypt the final encrypted result, thereby generating a plain text result set.

16. The computer program product of claim 15 , wherein the program instructions executable by a computing device further cause the computing device to:
output the plain text result set to a client that provided the range query.

17. A system comprising:
a memory; and
at least one processor coupled to the memory and configured for:
separately encrypting a set of plain text data using two or more encryption functions, thereby producing an encrypted domain comprising at least two distinct groups of encrypted data items, wherein the two or more encryption functions comprise (i) a brute force safe function and (ii) a range safe function;
converting a range query over plain text data items into a query over at least one of the distinct groups of encrypted data items; and
combining results from the query over the distinct groups of encrypted data items, thereby generating a final encrypted result to the range query.

18. A computer-implemented method, comprising steps of:
separately encrypting a table of plain text data using (i) a range safe encryption function and (ii) a brute force safe encryption function, thereby producing an encrypted table comprising (a) one or more columns of a range safe view of encrypted data and (b) one or more columns of a brute force safe view of encrypted data;
storing each column of (i) range safe view of encrypted data and (ii) brute force safe view of encrypted data in a distinct table;
removing physical and/or value correlations between the distinct tables;
converting a range query from the plain text data into a query over at least one of the distinct tables; and
combining results from the query over the distinct tables, thereby generating a final encrypted result to the range query;
wherein the steps are carried out by at least one computing device.

19. The computer-implemented method of claim 18 , comprising:
decrypting the final encrypted result, thereby generating a plain text result set; and
outputting the plain text result set to a client that provided the range query.

Assignees

• IBM

Inventors

• Deshpande Prasad M
• Haritsa Jayant R
• Kaul Akshar
• Kesarwani Manish
• Singh Gagandeep

Classifications

• H04L9/0618

  Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation · CPC title

• G06F21/6218 Primary

  to a system of files or objects, e.g. local or distributed file system or database · CPC title

• G06F21/62

  Protecting access to data via a platform, e.g. using keys or access control rules · CPC title

• G06F21/60

  Protecting data · CPC title

• H04L9/002

  Countermeasures against attacks on cryptographic mechanisms (network architectures or network communication protocols for protection against malicious traffic H04L63/1441) · CPC title