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 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 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 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 paired data items being non-deterministically encrypted ciphertext corresponding to the respective plaintext data item; 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. determining, 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; 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 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 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 paired data items being non-deterministically encrypted ciphertext corresponding to the respective plaintext data item; 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.