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.