Encrypted table indexes and searching encrypted tables
First Claim
Patent Images
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.
11 Assignments
0 Petitions
Accused Products
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.
190 Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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′
. - View Dependent Claims (10)
- less than”
-
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′
.
- greater than”
-
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. - View Dependent Claims (13, 14)
-
-
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. - View Dependent Claims (17, 18, 19)
-
-
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.
Specification