Deterministic encryption

A deterministic encryption scheme (as opposed to a probabilistic encryption scheme) is a cryptosystem which always produces the same ciphertext for a given plaintext and key, even over separate executions of the encryption algorithm. Examples of deterministic encryption algorithms include RSA cryptosystem (without encryption padding), and many block ciphers when used in ECB mode or with a constant initialization vector. A deterministic encryption scheme (as opposed to a probabilistic encryption scheme) is a cryptosystem which always produces the same ciphertext for a given plaintext and key, even over separate executions of the encryption algorithm. Examples of deterministic encryption algorithms include RSA cryptosystem (without encryption padding), and many block ciphers when used in ECB mode or with a constant initialization vector. Deterministic encryption can leak information to an eavesdropper, who may recognize known ciphertexts. For example, when an adversary learns that a given ciphertext corresponds to some interesting message, they can learn something every time that ciphertext is transmitted. To gain information about the meaning of various ciphertexts, an adversary might perform a statistical analysis of messages transmitted over an encrypted channel, or attempt to correlate ciphertexts with observed actions (e.g., noting that a given ciphertext is always received immediately before a submarine dive). This concern is particularly serious in the case of public key cryptography, where any party can encrypt chosen messages using a public encryption key. In this case, the adversary can build a large 'dictionary' of useful plaintext/ciphertext pairs, then observe the encrypted channel for matching ciphertexts. While deterministic encryption schemes can never be semantically secure, they have some advantages over probabilistic schemes. One primary motivation for the use of deterministic encryption is the efficient searching of encrypted data. Suppose a client wants to outsource a database to a possibly untrusted database service provider. If each entry is encrypted using a public-key cryptosystem, anyone can add to the database, and only the distinguished 'receiver' who has the private key can decrypt the database entries. If, however, the receiver wants to search for a specific record in the database, this becomes very difficult. There are some Public Key encryption schemes that allow keyword search, however these schemes all require search time linear in the database size. If the database entries were encrypted with a deterministic scheme and sorted, then a specific field of the database could be retrieved in logarithmic time.