A deterministic

encryption In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can dec ...

scheme (as opposed to a

probabilistic encryption Probabilistic encryption is the use of randomness in an encryption algorithm, so that when encrypting the same message several times it will, in general, yield different ciphertexts. The term "probabilistic encryption" is typically used in referen ...

scheme) is a

cryptosystem In cryptography, a cryptosystem is a suite of cryptographic algorithms needed to implement a particular security service, such as confidentiality (encryption). Typically, a cryptosystem consists of three algorithms: one for key generation, one f ...

which always produces the same

ciphertext In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext ...

for a given

plaintext In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted. Overview With the advent of com ...

and key, even over separate executions of the encryption algorithm. Examples of deterministic encryption algorithms include

RSA RSA may refer to: Organizations Academia and education * Rabbinical Seminary of America, a yeshiva in New York City *Regional Science Association International (formerly the Regional Science Association), a US-based learned society *Renaissance S ...

cryptosystem (without encryption padding), and many

block cipher In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called ''blocks''. Block ciphers are specified cryptographic primitive, elementary components in the design of many cryptographic protocols and ...

s when used in ECB mode or with a constant

initialization vector In cryptography, an initialization vector (IV) or starting variable (SV) is an input to a cryptographic primitive being used to provide the initial state. The IV is typically required to be random or pseudorandom, but sometimes an IV only needs to ...

Leakage

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 Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...

, 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.

Applications

While deterministic encryption schemes can never be semantically secure, they have some advantages over probabilistic schemes.

Database searching of encrypted data

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.

Security

Assuming that a deterministic encryption scheme is going to be used, it is important to understand what is the maximum level of security that can be guaranteed. A number of works have focused on this exact problem. The first work to rigorously define security for a deterministic scheme was in CRYPTO 2007. This work provided fairly strong security definitions (although weaker than semantic security), and gave constructions in the

random oracle In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time tha ...

model. Two follow-up works appeared the next year in CRYPTO 2008, giving definitional equivalences and constructions without random oracles.

Alternatives to deterministic encryption

To counter this problem, cryptographers proposed the notion of "randomized" or

. Under these schemes, a given plaintext can encrypt to one of a very large set of possible ciphertexts, chosen randomly during the encryption process. Under sufficiently strong security guarantees the attacks proposed above become infeasible, as the adversary will be unable to correlate any two encryptions of the same message, or correlate a message to its ciphertext, even given access to the public encryption key. This guarantee is known as

semantic security In cryptography, a semantically secure cryptosystem is one where only negligible information about the plaintext can be feasibly extracted from the ciphertext. Specifically, any probabilistic, polynomial-time algorithm (PPTA) that is given the cip ...

ciphertext indistinguishability Ciphertext indistinguishability is a property of many encryption schemes. Intuitively, if a cryptosystem possesses the property of indistinguishability, then an adversary will be unable to distinguish pairs of ciphertexts based on the message t ...

, and has several definitions depending on the assumed capabilities of the attacker (see

References

{{reflist *Mihir Bellare and Alexandra Boldyreva and Adam O'Neill, Deterministic and Efficiently Searchable Encryption, CRYPTO 200

*Alexandra Boldyreva and Serge Fehr and Adam O'Neill, On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles, CRYPTO 200

*Mihir Bellare and Marc Fischlin and Adam O'Neill and Thomas Ristenpart, Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles, CRYPTO 200

Theory of cryptography

Leakage

Applications

Database searching of encrypted data

Security

Alternatives to deterministic encryption

See also

References