Encrypted table indexes and searching encrypted tables

• US 20060041533A1
• Filed: 05/20/2004
• Published: 02/23/2006
• Est. Priority Date: 05/20/2004
• Status: Active Grant

• Current Assignee: Thales DIS CPL USA, Inc. (Thales SA)
• Original Assignee: SafeNet Incorporated (Thales SA)
• Inventors: Koyfman, Andrew
• Granted Patent: US 7,519,835 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: H04L 9/0897 involving additional devices, e.g. trusted platform module [TPM], smartcard or USB
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

The present invention teaches a variety of methods for building and searching secure, indexed database tables. Sensitive portions of the database tables and database indexes are encrypted, ordered and searched according to Boolean functions arranged to work with encrypted data. Also disclosed is a database management system that allows authorized users to build and search encrypted tables.

Claims

1. A computer implemented method for building an encrypted database index for searching a database table, said method comprising:

forming a database table including at least a row ID column having a plurality of row ID fields, and a sensitive data column having a plurality of sensitive data fields;

populating a plurality of nodes, each node having both an index key being data from a unique one of said plurality of sensitive data fields and an index data being data from a unique one of said plurality of row ID fields, whereby said nodes include a plurality of index keys and a plurality of index data;

encrypting said plurality of index keys found in said plurality of nodes; and

ordering said plurality of nodes.

2. A computer-implemented method as recited in claim 1, wherein said act of forming a database table includes forming a database table having a plurality of field columns.

3. A computer-implemented method as recited in claim 1, wherein said act of encrypting said plurality of index keys is performed using a first private key.

4. A computer-implemented method as recited in claim 3, further comprising encrypting said plurality of index data using said first private key.

5. A computer-implemented method as recited in claim 4, further comprising encrypting data from said plurality of row ID fields.

6. A computer-implemented method as recited in claim 5 wherein said act of encrypting data from said plurality of row ID fields uses a second private key.

7. A computer-implemented method as recited in claim 1 further comprising deleting the transparent data corresponding to said plurality of index keys so that only the encrypted plurality of index keys remains.

8. A computer-implemented method as recited in claim 1 further comprising storing said encrypted database table and said encrypted plurality of nodes to a persistent memory.

9. A computer readable medium comprising computer executable instructions for a “

less than”

comparitor function useful for comparing two encrypted data A and B, said computer executable instructions including;

receiving data A and B in an encrypted format;

decrypting A to form A′

;

decrypting B to form B′

;

performing a “

less than”

operation appropriate to a common data type of data A′ and

B′

; and

returning results from said “

less than”

operation appropriate to a common data type of data A′ and

B′

.

10. A computer readable medium comprising computer executable instructions for a “

less than”

comparitor function useful for comparing two encrypted data A and B as recited in claim 9, said computer executable instructions further including determining whether an entity requesting an operation of said “

less than”

function is authorized to perform encryption operations.

11. A computer readable medium comprising computer executable instructions for a “

greater than”

comparitor function useful for comparing two encrypted data A and B, said computer executable instructions including;

receiving data A and B in an encrypted format;

decrypting A to form A′

;

decrypting B to form B′

;

performing a “

greater than”

operation appropriate to a common data type of data A′ and

B′

; and

returning results from said “

greater than”

operation appropriate to a common data type of data A′ and

B′

.

12. A secure index for indexing a database table, said secure index searchable only by users authorized to utilize encryption functions available on said computer system, said secure index comprising:

a plurality of nodes, each node including an index key and an index data, each index key being encrypted, decrypted data from each index key providing meaningful information, and each index data identifying a storage location within said database table; and

wherein said plurality of nodes is logically ordered in a manner searchable only through decryption.

13. A secure index as recited in claim 12, wherein each of said index data are encrypted according to a first private encryption key.

14. A secure index as recited in claim 13, wherein data found in fields in said database table corresponding to said index data is encrypted according to a second private encryption key different from said first private encryption key.

15. A method for searching an encrypted database table via a secure index, said secure index having a plurality of nodes, each node including an index key and an index data, each index key being encrypted, decrypted data from each index key providing meaningful information, and each index data identifying a storage location within said database table, and wherein said plurality of nodes is logically ordered in a manner searchable only through decryption, said method comprising:

receiving a request to search said secure index from a user;

determining whether said user is authorized to utilize encryption functions;

when said user is authorized to utilize encryption functions, performing said requested search using one or more comparison functions operable to decrypt indexed and encrypted data.

16. A computer system comprising:

an encrypted database;

a database table including at least a row ID column having a plurality of row ID fields, and a sensitive data column having a plurality of sensitive data fields, said row ID column and said sensitive data column encrypted;

a database index corresponding to said database table, said database index including a plurality of nodes, each node having both an index key being data from a unique one of said plurality of sensitive data fields and an index data being data from a unique one of said plurality of row ID fields, whereby said nodes include a plurality of index keys and a plurality of index data, said plurality of index keys being encrypted, said plurality of nodes being ordered according to said encrypted index keys; and

a database management system instantiated on said computer system, said database management system operable to search said database table using said database index.

17. A computer system as recited in claim 16, wherein said computer system further comprises a cryptographic service engine operable to perform cryptographic functions as requested by said database management system.

18. A computer system as recited in claim 17, wherein said cryptographic service engine provides computer executable instructions for a “

less than”

comparitor function useful for comparing two encrypted data A and B, said computer executable instructions including;

receiving data A and B in an encrypted format;

decrypting A to form A′

;

decrypting B to form B′

;

performing a “

less than”

operation appropriate to a common data type of data A′ and

B′

; and

returning results from said “

less than”

operation appropriate to a common data type of data A′ and

B′

.

19. A computer system as recited in claim 17, further comprising an cryptographic API which provides an interface to said cryptographic service engine for applications running on said computer system.

20. A computer database having a database table and a database index, said computer database characterized in that:

sensitive portions of said database table and said database index are encrypted, said database index ordered and searched according to Boolean functions arranged to work with encrypted data.