Structure Preserving Database Encryption Method and System

• US 20080133935A1
• Filed: 06/16/2006
• Published: 06/05/2008
• Est. Priority Date: 06/01/2004
• Status: Active Grant

• Current Assignee: Ben Gurion University of The Negev
• Original Assignee: Ben Gurion University of The Negev
• Inventors: Elovici, Yuval, Vaisenberg, Ronen, Shmueli, Erez
• Granted Patent: US 8,639,947 B2
• Time in Patent Office: Days
• US Class Current: 713/193
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: H04L 63/062 for key distribution, e.g. centrally by trusted party cryptographic mechanisms or cryptographic arrangements for key distribution involving a central third party H04L9/0819
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• 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/0836 using tree structure or hierarchical structure
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms

Abstract

A database encryption system and method, the Structure Preserving Database Encryption (SPDE), is presented. In the SPDE method, each database cell is encrypted with its unique position. The SPDE method permits to convert a conventional database index into a secure one, so that the time complexity of all queries is maintained. No one with access to the encrypted database can learn anything about its content without the encryption key. Also a secure index for an encrypted database is provided. Furthermore, secure database indexing system and method are described, providing protection against information leakage and unauthorized modifications by using encryption, dummy values and pooling, and supporting discretionary access control in a multi-user environment.

Claims

1. A Structure Preserving Database Encryption system for a database encryption, comprising:

a. a client for;

a.1. receiving one or more encryption keys, according to the client'"'"'s access right definition;

a.2. generating a session;

a.3. transferring to said database server said one or more encryption keys; and

a.4. generating at least one query; and

b. an authentication server for identifying said client and transferring to him said one or more encryption keys; and

c. a database server for;

c.1. communicating with said client by means of said session generated by said client;

c.2. searching an encrypted database for the corresponding data requested in said at least one query;

c.3. after finding said corresponding data, decrypting said corresponding data by means of said one or more encryption keys; and

c.4. transferring the results of said at least one query to said client.

2. A Structure Preserving Database Encryption method for a database encryption, comprising:

a. identifying a client by means of an authentication server communicating over a conventional identification protocol;

b. receiving one or more encryption keys from said authentication server by the client, said one or more encryption keys being relevant for performing at least one query of said client, according to the client'"'"'s access right definition;

c. generating a session by means of said client with a database server;

d. transferring from said client to said database server the corresponding one or more encryption keys received from said an authentication server;

e. generating said at least one query by the client;

f. searching by means of said database server an encrypted database for the corresponding data requested in said at least one query;

g. after finding said corresponding data, decrypting said corresponding data by means of said one or more corresponding encryption keys; and

h. transferring the results of said at least one query from said database server to said client.

3. A Structure Preserving Database Encryption method for a database encryption, said database consisting of at least one table having one or more rows, columns and cells, comprising the steps of the encryption of each cell value:

a. determining a value stored in a corresponding cell;

b. determining the position of said cell within a database by determining said cell table, row and column identifiers;

c. activating a function concatenating said cell table, row and column identifiers and as a result of said concatenating obtaining a number based on said identifiers;

d. performing a XOR operation between said number and said value stored in said cell or concatenating said number with said value stored in said cell; and

e. activating an encryption function on a result obtained from said XOR operation or said concatenating of said number with said value stored in said cell.

4. Method according to claim 3, further comprising:

a. activating a hash function on the result of the concatenating and as a result obtaining another number based on the cell table, row and column identifiers;

b. performing a XOR operation between said another number and the value stored in the cell or concatenating said another number with said value stored in said cell; and

c. activating an encryption function on a result obtained from said XOR operation or the concatenating of said another number with said value stored in said cell.

5. Method according to claim 3, further comprising the steps of the decryption of each cell value:

a. activating on an encrypted value a decryption function which decrypts said encrypted value and as a result a decrypted value is obtained; and

b. performing a XOR operation between said decrypted value and the number obtained as the result of the concatenating the cell table, row and column identifiers.

6. Method according to claim 4, further comprising the steps of the decryption of each cell value:

a. activating on an encrypted value a decryption function which decrypts said encrypted value and as a result a decrypted value is obtained; and

b. performing the XOR operation between said decrypted value and another number obtained as the result of activating the hash function or performing discarding said another number from said decrypted value.

7. A method for database encryption, wherein said database comprise an index consisting of values of at least one table having one or more rows, columns and cells, said method comprising the steps of the encryption of each index entry:

a. determining a value stored in a corresponding cell;

b. concatenating said value stored in said cell with a random number having a fixed number of bits or concatenating said value stored in said cell with a row identifier of said cell; and

c. activating an encryption function on a result obtained from said concatenating.

8. Method according to claim 7, further comprising the steps of the encryption of each index entry:

a. obtaining an internal pointer to index entries;

b. obtaining an external pointer to a corresponding row in a table wherein said value is stored;

c. encrypting said external pointer by means of a conventional encryption function; and

d. activating an authentication code function, said authentication code function;

d.1. concatenating together;

i. the value stored in the corresponding cell;

ii. said internal pointer to index entries;

iii. said external pointer said corresponding row in the table wherein said value is stored; and

iv. an entry self pointer; and

d.2. calculating a message authentication code value from said concatenating.

9. Method according to claim 8, further comprising:

a. defining a fixed size pool for each index, said pool holding one or more values for inserting into the corresponding index; and

b. updating said each index with corresponding said one or more values only if said pool is full.

10. Method according to claim 9, further comprising extracting corresponding values from the corresponding pool to the corresponding index in a random order.

11. A method for executing a client'"'"'s query in an encrypted-index database, by means of a database server using sub-indexes, comprising:

a. connecting to a database server by means of a client and identifying said client;

b. creating a secure session between said database server and said client;

c. transferring one or more encryption keys by means of said client to said database server;

d. submitting a query by means of said client to said database server;

e. locating corresponding sub-indexes which said client is entitled to access;

f. executing said query on said corresponding sub-indexes by means of said database server using said one or more encryption keys; and

g. transferring a result of said query to said client.