Encrypted data search

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.

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.