Entropic security
Encyclopedia
Entropic security is a security definition used in the field of cryptography
. Modern encryption
schemes are generally required to protect communications even when the attacker has substantial information about the messages being encrypted. For example, even if an attacker knows that an intercepted ciphertext
encrypts either the message "Attack" or the message "Retreat", a semantically secure encryption scheme will prevent the attacker from learning which of the two messages is encrypted. However, definitions such as semantic security
are too strong to achieve with certain specialized encryption schemes. Entropic security is a weaker definition that can be used in the special case where an attacker has very little information about the messages being encrypted.
It is well known that certain types of encryption algorithm cannot satisfy definitions such as semantic security
: for example, deterministic encryption
algorithms can never be semantically secure. Entropic security definitions relax these definitions to cases where the message space has substantial entropy (from an adversary's
point of view). Under this definition it is possible to prove security of deterministic encryption.
Note that in practice entropically-secure encryption algorithms are only "secure" provided that the message distribution possesses high entropy from any reasonable adversary's perspective. This is an unrealistic assumption for a general encryption scheme, since one cannot assume that all likely users will encrypt high-entropy messages. For these schemes, stronger definitions (such as semantic security or indistinguishability under adaptive chosen ciphertext attack) are appropriate. However, there are special cases in which it is reasonable to require high entropy messages. For example, encryption schemes that encrypt only secret key material (e.g., key encapsulation
or Key Wrap
schemes) can be considered under an entropic security definition. A practical application of this result is the use of deterministic encryption
algorithms for secure encryption of secret key material.
Russell and Wang formalized a definition of entropic security for encryption. Their definition resembles the semantic security
definition when message spaces have highly-entropic distribution. In one formalization, the definition implies that an adversary given the ciphetext will be unable to compute any predicate on the ciphertext with (substantially) greater probability than an adversary who does not possess the ciphertext. Dodis and Smith later proposed alternate definitions and showed equivalence.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
. Modern encryption
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...
schemes are generally required to protect communications even when the attacker has substantial information about the messages being encrypted. For example, even if an attacker knows that an intercepted 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...
encrypts either the message "Attack" or the message "Retreat", a semantically secure encryption scheme will prevent the attacker from learning which of the two messages is encrypted. However, definitions such 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...
are too strong to achieve with certain specialized encryption schemes. Entropic security is a weaker definition that can be used in the special case where an attacker has very little information about the messages being encrypted.
It is well known that certain types of encryption algorithm cannot satisfy definitions such 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...
: for example, deterministic encryption
Deterministic encryption
A deterministic 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...
algorithms can never be semantically secure. Entropic security definitions relax these definitions to cases where the message space has substantial entropy (from an adversary's
Adversary (cryptography)
In cryptography, an adversary is a malicious entity whose aim is to prevent the users of the cryptosystem from achieving their goal...
point of view). Under this definition it is possible to prove security of deterministic encryption.
Note that in practice entropically-secure encryption algorithms are only "secure" provided that the message distribution possesses high entropy from any reasonable adversary's perspective. This is an unrealistic assumption for a general encryption scheme, since one cannot assume that all likely users will encrypt high-entropy messages. For these schemes, stronger definitions (such as semantic security or indistinguishability under adaptive chosen ciphertext attack) are appropriate. However, there are special cases in which it is reasonable to require high entropy messages. For example, encryption schemes that encrypt only secret key material (e.g., key encapsulation
Key encapsulation
Key encapsulation mechanisms are a class of encryption techniques designed to secure symmetric cryptographic key material for transmission using asymmetric algorithms. In practice, public key systems are clumsy to use in transmitting long messages. Instead they are often used to exchange...
or Key Wrap
Key Wrap
Key Wrap constructions are a class of symmetric encryption algorithms designed to encapsulate cryptographic key material. The Key Wrap algorithms are intended for applications such as protecting keys while in untrusted storage, or transmitting keys over untrusted communications networks...
schemes) can be considered under an entropic security definition. A practical application of this result is the use of deterministic encryption
Deterministic encryption
A deterministic 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...
algorithms for secure encryption of secret key material.
Russell and Wang formalized a definition of entropic security for encryption. Their definition resembles the 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...
definition when message spaces have highly-entropic distribution. In one formalization, the definition implies that an adversary given the ciphetext will be unable to compute any predicate on the ciphertext with (substantially) greater probability than an adversary who does not possess the ciphertext. Dodis and Smith later proposed alternate definitions and showed equivalence.