Cryptography: Notions of security

This article briefly discusses the relations between the following notions of security:

• Ciphertext integrity
• Ciphertext indistinguishability
• Semantic security
• Existential unforgeability
• Collision resistance

Ciphertext integrity

It is computationally infeasible to create a ciphertext that decrypts correctly. More precisely, if the decryption key is chosen at random, then a ciphertext forged in polynomial time fails to decrypt by that key with very high probability. The main purpose of CI is to ensure that the ciphertext is not modified during the transmission from the sender to the receiver. Note that when we say CI, we actually means CI under CPA.

• In general, good encryption does not necessarily imply integrity.
• Encryption schemes that never reject cannot be CI. For example, CBC with random IV never rejects a ciphertext, hence the adversary easily wins CI game.

Ciphertext indistinguishability

It is computationally infeasible to distinguish two ciphertexts with respect to their plaintexts. More precisely, given two plaintexts $m_0, m_1$ such that $|m_0|=|m_1|$ and $c\in_r\{E(k,m_0),E(k,m_1)\}$, a polynomial-time adversary has no efficient way to tell the plaintext of $c$ significantly better than random guess. Ciphertext indistinguishability (IND) is identified by the type of attack and can be ordered according to their strength of security as follows: IND-CPA < IND-CCA1 < IND-CCA2. Note that IND-CPA plus CI imply IND-CCA1.

An encryption system with ciphertext indistinguishability must be randomized. For public key encryption system, the adversary have an public key issued by the challenger, and thus he can encrypt any plaintexts at his disposal. However, the probabilistic nature of the encryption means that the ciphertexts are nearly random, and therefore encrypting $m_0, m_1$ and comparing the resulting ciphertexts with the challenge ciphertext does not afford any non-negligible advantage to the adversary.

Semantic security

It is computationally infeasible to learn information about the plaintext from the ciphertext. More precisely, if two plaintexts $m_0, m_1$ satisfy $|m_0|=|m_1|$, then $\{E(k, m_0)\} \approx_p \{E(k, m_1)\}$. Note that when we say semantic security, we actually mean semantic security under CPA. Hence, the two probability distributions above are in fact conditioned on a polynomial number of plaintext-ciphertext pairs where the plaintexts are chosen by the adversary.

Semantic security is shown to be equivalent to IND-CPA, and many cryptographic proofs use these two definitions interchangeably. Like IND, deterministic encryption cannot be semantically secure.

Existential unforgeability

It is computationally infeasible to forge a message along with a correct tag. More precisely, if $(S_k,V_k)$ is a MAC with existential unforgeability and a polynomial-time adversary forges $m,t$ without $k$, then $V_k(m,t)=0$ with very high probability. Note that when we say existential unforgeability, we actually mean existential unforgeability under CPA, ie., the adversary can request a polynomial number of messages for their tags before the challenge.

Fact. Let $(E,D)$ be a symmetric encryption system and define a MAC by letting $T_k(m)=E(k,m)$ and $V_k(m,t)=1$ iff $D(k,m)=t$. Then this MAC has existential unforgeability iff the encryption system has ciphertext integrity.

Collision resistance

It is computationally infeasible to find two inputs with the same output. More precisely, if $H$ is a function with collision resistance, then no polynomial-time adversary can find $m_1\neq m_2$ such that $H(m_1)=H(m_2)$ with a chance significantly better than random guess. Collision resistance is a property of a cryptographic hash function, among the following two properties: (i) Preimage resistance: For any element in the image, it is computationally infeasible to find its preimage; (ii) Second-preimage resistance: For any element in the domain, it is computationally infeasible to find another element in the domain with the same image.