Deterministic encryption

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 the 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, 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. [1], [2],[3]), 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, [4]. 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 [5], [6].


  • Mihir Bellare and Alexandra Boldyreva and Adam O'Neill, Deterministic and Efficiently Searchable Encryption, CRYPTO 2007 [7] [8]
  • Alexandra Boldyreva and Serge Fehr and Adam O'Neill, On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles, CRYPTO 2008 [9] [10]
  • Mihir Bellare and Marc Fischlin and Adam O'Neill and Thomas Ristenpart, Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles, CRYPTO 2008 [11] [12]

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • 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 reference to public key… …   Wikipedia

  • Optimal asymmetric encryption padding — This article is about the padding scheme used in public key cryptography. For the division of the Thailand Ministry of Science Technology and Environment entitled Office of Atomic Energy for Peace, see [1]. In cryptography, Optimal Asymmetric… …   Wikipedia

  • Optimal Asymmetric Encryption Padding — This article is about the padding scheme used in public key cryptography. For the division of the Thailand Ministry of Science Technology and Environment entitled Office of Atomic Energy for Peace, see [] …   Wikipedia

  • Entropic security — is a security definition for encryption for specific message spaces. Standard security definitions such as semantic security permit the adversary a great deal of knowledge about the messages being encrypted for example, the adversary is often… …   Wikipedia

  • RSA — In cryptography, RSA is an algorithm for public key cryptography. It is the first algorithm known to be suitable for signing as well as encryption, and one of the first great advances in public key cryptography. RSA is widely used in electronic… …   Wikipedia

  • 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… …   Wikipedia

  • Key Wrap — constructions are a class of symmetric encryption algorithms designed to encapsulate (encrypt) cryptographic key material. The Key Wrap algorithms are intended for applications such as (a) protecting keys while in untrusted storage, or (b)… …   Wikipedia

  • детерминированное шифрование — Каждому открытому тексту сообщения ставится в соответствие ровно один шифрованный текст. [ d=23] Тематики защита информации EN deterministic encryption …   Справочник технического переводчика

  • One-time pad — Excerpt from a one time pad In cryptography, the one time pad (OTP) is a type of encryption, which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit …   Wikipedia

  • Cryptographic hash function — A cryptographic hash function (specifically, SHA 1) at work. Note that even small changes in the source input (here in the word over ) drastically change the resulting output, by the so called avalanche effect. A cryptographic hash function is a… …   Wikipedia