Encrypted data search

• US 20080059414A1
• Filed: 09/06/2006
• Published: 03/06/2008
• Est. Priority Date: 09/06/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dutta, Tanmoy, Garcia, Raul, Cristofor, Elena Daniela, Cristofor, Laurentiu Bogdan, Hsueh, Sung L.
• Granted Patent: US 7,689,547 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 21/606 by securing the transmission between two devices or processes
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

An indexing value may be determined, transparently with respect to a requester, based on a desired plaintext item of data and a cryptographic key. The indexing value may be used to access an entry in an indexing structure to obtain a corresponding database entry which includes a non-deterministically encrypted ciphertext item. In another embodiment, an indexing structure for a database may be accessed. Positions of items of the indexing structure may be based on corresponding plaintext items. References related to the corresponding plaintext items in the indexing structure may be encrypted and other information in the indexing structure may be unencrypted. A portion of the indexing structure may be loaded into a memory and at least one of the encrypted references related to one of the plaintext items may be decrypted. The decrypted reference may be used to access a corresponding non-deterministically encrypted data item from the database.

Claims

1. A method for performing a search on non-deterministically encrypted data in a database system, the method comprising:

determining, transparently to a user, an indexing value for a desired plaintext item of data provided by the user, the indexing value being based, at least partially on the desired plaintext item of data and a cryptographic key;

using the indexing value to access a corresponding entry in an indexing structure to obtain a database entry including non-deterministically encrypted ciphertext corresponding to the desired plaintext item of data.

2. The method of claim 1, wherein the determining of the indexing value for a desired plaintext item of data further comprises:

calculating a message authentication code based on the desired plaintext item of data.

3. The method of claim 1, wherein the indexing structure includes at least a first item of each of a plurality of paired data items, the first item of each of the plurality of paired data items being an indexing data item having a value based on a respective plaintext data item and the cryptographic key and a second item of each of the paired data items being ciphertext corresponding to the respective plaintext data item.

4. The method of claim 1, wherein

the indexing structure includes at least a first item of each of a plurality of paired data items, the first item of each of the paired data items being an indexing data item having a value based on applying a hashed message authentication code and the cryptographic key to a respective plaintext data item and a second item of each of the paired data items being ciphertext corresponding to the respective plaintext data item.

5. The method of claim 1, wherein:

the indexing structure includes at least a first item of each of a plurality of paired data items, the first item of each of the paired data items being an indexing data item having a value based on applying a hashed message authentication code and the cryptographic key to a respective plaintext data item and a second item of each of the paired data items being ciphertext corresponding to the respective plaintext data item, and

the method further comprises;

using the indexing value to obtain a second item of a corresponding one of the paired data items;

decrypting the second item of the corresponding one of the paired data items; and

comparing the decrypted second item of the corresponding one of the paired data items with the desired plaintext item of data to determine whether a hash collision occurred.

6. The method of claim 1, wherein the determining an indexing value for a desired plaintext data item further comprises:

calculating a message authentication code based on the cryptographic key and the desired plaintext data item; and

hashing the calculated message authentication code to determine the indexing value.

7. The method of claim 1, wherein the indexing structure includes a plurality of hash buckets allocated for respective items according to a hashed message authentication code of a corresponding plaintext item of data.

8. A machine-readable medium having instructions stored therein for at least one processor, the machine-readable medium comprising:

instructions for accessing an indexing structure for a database, a position of items in the indexing structure being based on corresponding plaintext items, references related to the corresponding plaintext items in the indexing structure being encrypted and other information in the indexing structure being unencrypted;

instructions for loading at least a portion of the indexing structure into a memory;

instructions for decrypting at least one of the references related to a corresponding one of the plaintext items in the at least a portion of the indexing structure; and

instructions for using the decrypted at least one of the references to access a corresponding non-deterministically encrypted data item from the database.

9. The machine-readable medium of claim 8, wherein:

the instructions for decrypting at least one of the references related to the corresponding plaintext item in the at least a portion of the indexing structure are executed when a page of the indexing structure is loaded into the memory.

10. The machine-readable memory of claim 8, wherein:

the instructions for decrypting at least one of the references related to the corresponding plaintext item in the at least a portion of the indexing structure are executed when the at least a portion of the indexing structure is used to search for non-deterministically encrypted data in the database corresponding to a desired data item.

11. The machine-readable medium of claim 8, wherein the encrypted references related to the corresponding plaintext item include plaintext statistics.

12. The machine-readable medium of claim 8, wherein the indexing structure includes a B-tree.

13. The machine-readable medium of claim 8, wherein the encrypted references related to the corresponding plaintext items in the indexing structure are encrypted with a same key used to encrypt non-deterministically encrypted data items stored in the database.

14. The machine-readable medium of claim 8, further comprising:

instructions for searching the at least a portion of the indexing structure to access one or more non-deterministically encrypted data items from the database corresponding to a desired range of data items.

15. A method for providing a remote database for performing a search on non-deterministically encrypted data in a database system, the method comprising:

receiving a remote request from a requester, via a network, to search the non-deterministically encrypted data in the database system for a database entry corresponding to a desired plaintext data item;

calculating, transparently to the requester, a code based on the desired plaintext data item and a cryptographic key;

using the code as an index to an indexing structure to obtain the database entry corresponding to the desired plaintext data item; and

returning data to the requester, the returned data including the database entry corresponding to the desired plaintext data item obtained from the database system.

16. The method of claim 15, wherein the calculating of a code based on the desired plaintext data item and a cryptographic key further comprises calculating a hashed message authentication code.

17. The method of claim 15, wherein the indexing structure comprises a plurality of items, each of the plurality of items including at least a first item of a duplet and a second item of the duplet, the first item of the duplet comprises a code based on a corresponding plaintext data item and the cryptographic key, the second item of the duplet comprises non-deterministically encrypted ciphertext corresponding to the respective plaintext data item

18. The method of claim 15, wherein the indexing structure comprises a plurality of items, each of the plurality of items including at least a first item of a duplet and a reference to a second item of the duplet, the first item of the duplet comprises a code based on a corresponding plaintext data item and the cryptographic key, the reference to the second item of the duplet includes a pointer to a data structure including the second item of the duplet, and the second item of the duplet includes non-deterministically encrypted ciphertext corresponding to the respective plaintext data item.

19. The method of claim 15, wherein the indexing structure includes a plurality of hash buckets allocated for respective items according to a corresponding hash value, the corresponding hash value being determined by calculating a hashed message authentication code based on a corresponding plaintext data item and the cryptographic key, and hashing the calculated hashed message authentication code to produce the corresponding hash value.

20. The method of claim 15, wherein the indexing structure includes a B-tree.