Encrypted table indexes and searching encrypted tables

• US 7,519,835 B2
• Filed: 05/20/2004
• Issued: 04/14/2009
• 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
• Primary Examiner(s): Revak; Christopher A
• Application Number:
  US10/850,827
• Publication Number:
  US 20060041533A1
• Time in Patent Office: 1,790 Days
• Field of Search: None
• US Class Current: 713/193
• 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 a database having no un-encrypted database table, said method comprising:

forming a transparent 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 with the transparent table, 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;

ordering said plurality of nodes according to values of said encrypted index keys;

encrypting the plurality of sensitive data fields and forming an at least partially encrypted database table in the database;

deleting the transparent table.

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 1 wherein said act of encrypting the plurality of sensitive data fields uses a second private key.

6. 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.

7. A computer-implemented method as recited in claim 1

wherein said act of ordering said plurality of nodes further comprises:

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′

.

8. A computer-implemented method as recited in claim 7, further including determining whether an entity requesting an operation of said “

less than”

function is authorized to perform encryption operations.

9. A computer-implemented method as recited in claim 1

wherein said act of ordering said plurality of nodes further comprises:

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′

.

10. A computer-implemented secure index for indexing an at least partially encrypted database table, said secure index searchable only by users authorized to utilize encryption functions available on a 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 in an encrypted database having no un-encrypted database table; and

wherein said plurality of nodes are logically ordered according to value of said encrypted index key of each said node in a manner searchable only through decryption.

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

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

13. A method for searching an at least partially 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 in an encrypted database having no un-encrypted database table, and wherein said plurality of nodes is logically ordered according to value of said encrypted index key of each said node 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.

14. A computer system comprising:

an encrypted database having no un-encrypted database table;

a database table in the encrypted database 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 values of 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.

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

16. A computer system as recited in claim 15, 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′

.

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