Encrypted data search

• US 7,689,547 B2
• Filed: 09/06/2006
• Issued: 03/30/2010
• Est. Priority Date: 09/06/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dutta, Tanmoy, Cristofor, Elena Daniela, Cristofor, Laurentiu Bogdan, Hsueh, Sung L., Garcia, Raul
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Spieler; William
• Application Number:
  US11/516,267
• Publication Number:
  US 20080059414A1
• Time in Patent Office: 1,301 Days
• Field of Search: 707/2, 707/3, 380/59, 380/28, 713/189, 726/26
• US Class Current: 707/715
• 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, by a processor and transparently to a user, an indexing value for a desired plaintext item of data provided by the user, the determining further comprising;

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

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

using, by the processor, 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, the indexing structure including a first item of each of a plurality of paired data items, and either a second item of each of the plurality of paired data items or a reference to the second item of each of the 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 applying a hashed message authentication code, using the cryptographic key, over a respective plaintext item of data and the second item of each of the plurality of paired data items being non-deterministically encrypted ciphertext corresponding to the respective plaintext item of data;

decrypting, by the processor, the second item of a corresponding one of the plurality of paired data items; and

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

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

3. 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, by a processor and transparently to the requester, a code based on the desired plaintext data item and a cryptographic key;

using, by the processor, the code as an index to an indexing structure to obtain the database entry corresponding to the desired plaintext data item, the indexing structure including a plurality of hash buckets 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;

decrypting, by the processor, a non-deterministically encrypted item of an entry of the indexing structure corresponding to the code;

comparing, by the processor, the decrypted non-deterministically encrypted item of the entry of the indexing structure with the desired plaintext data item to determine whether a hash collision occurred; 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.

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

5. The method of claim 3, wherein the indexing structure further comprises a plurality of items, each of the plurality of items including at least a first item of a duplet and either a second item of the duplet or a reference to the second item of the duplet, the first item of the duplet comprises a code corresponding to a respective plaintext data item, and the second item of the duplet comprises non-deterministically encrypted ciphertext corresponding to the respective plaintext data item.

6. The method of claim 3, wherein the indexing structure includes a B-tree.

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

instructions for calculating a message authentication code based on a desired plaintext item of data and a cryptographic key, and

instructions for hashing the calculated message authentication code to determine an indexing value;

instructions for 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, the indexing structure including a first item of each of a plurality of paired data items, and either a second item of each of the plurality of paired data items or a reference to the second item of each of the 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 applying a hashed message authentication code, using the cryptographic key, over a respective plaintext item of data and the second item of each of the plurality of paired data items being non-deterministically encrypted ciphertext corresponding to the respective plaintext item of data;

instructions for using the indexing value to obtain a second item of a paired data item of the corresponding entry of the indexing structure;

instructions for decrypting the second item of the paired data item of the corresponding entry of the indexing structure; and

instructions for comparing the decrypted second item of the corresponding entry of the indexing structure with the desired plaintext item of data to determine whether a hash collision occurred.