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.