Deterministic encryption
Encyclopedia
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 the RSA cryptosystem (without encryption padding), and many block cipher
s 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, she learns 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 dives). 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.
To counter this problem, cryptographers proposed the notion of "randomized" or probabilistic encryption
. 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
or indistinguishability, and has several definitions depending on the assumed capabilities of the attacker (see semantic security
).
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 secret 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 (e.g. http://citeseer.ist.psu.edu/old/690883.html, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.7432,http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.2584), 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. 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 recent works have focused on this exact problem. The first work to rigorously define security for a deterministic scheme was in CRYPTO 2007
, http://www.springerlink.com/content/18256529p5211276/. This work provided fairly strong security definitions (although weaker than semantic security), and gave constructions in the random oracle
model. Two follow-up works appeared the next year in CRYPTO 2008, giving definitional equivalences and constructions without random oracles http://www.springerlink.com/content/f57uh254577q7u43/, http://www.springerlink.com/content/e1485v36wm2721wp/.
Encryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
scheme (as opposed to a probabilistic encryption
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...
scheme) is a cryptosystem
Cryptosystem
There are two different meanings of the word cryptosystem. One is used by the cryptographic community, while the other is the meaning understood by the public.- General meaning :...
which always produces the same ciphertext
Ciphertext
In cryptography, ciphertext 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 that is unreadable by a human or computer without the proper cipher...
for a given plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
and key, even over separate executions of the encryption algorithm. Examples of deterministic encryption algorithms include the RSA cryptosystem (without encryption padding), and many block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
s when used in ECB mode or with a constant initialization vector
Initialization vector
In cryptography, an initialization vector is a fixed-size input to a cryptographic primitive that is typically required to be random or pseudorandom...
.
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, she learns 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 dives). 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.
To counter this problem, cryptographers proposed the notion of "randomized" or probabilistic encryption
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...
. 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
Semantic security
Semantic security is a widely used definition for security in an asymmetric key encryption algorithm. For a cryptosystem to be semantically secure, it must be infeasible for a computationally bounded adversary to derive significant information about a message when given only its ciphertext and...
or indistinguishability, and has several definitions depending on the assumed capabilities of the attacker (see semantic security
Semantic security
Semantic security is a widely used definition for security in an asymmetric key encryption algorithm. For a cryptosystem to be semantically secure, it must be infeasible for a computationally bounded adversary to derive significant information about a message when given only its ciphertext and...
).
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 secret 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 (e.g. http://citeseer.ist.psu.edu/old/690883.html, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.7432,http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.2584), 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. 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 recent works have focused on this exact problem. The first work to rigorously define security for a deterministic scheme was in CRYPTO 2007
CRYPTO (conference)
CRYPTO, the International Cryptology Conference, is one of the largest academic conferences in cryptography and cryptanalysis. It is organized by the International Association for Cryptologic Research , and it is held yearly in August in Santa Barbara, California at the University of California,...
, http://www.springerlink.com/content/18256529p5211276/. This work provided fairly strong security definitions (although weaker than semantic security), and gave constructions in the random oracle
Random oracle
In cryptography, a random oracle is an oracle that responds to every query with a random response chosen uniformly from its output domain, except that for any specific query, it responds the same way every time it receives that query...
model. Two follow-up works appeared the next year in CRYPTO 2008, giving definitional equivalences and constructions without random oracles http://www.springerlink.com/content/f57uh254577q7u43/, http://www.springerlink.com/content/e1485v36wm2721wp/.