Provable security notes / IV

Encryption definitions

Encryption security depends on what the adversary may query and what it has to distinguish.

An encryption theorem is meaningless until the attack game is fixed. For a public-key scheme

\[\Pi=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec}),\]

correctness says that honestly generated ciphertexts decrypt to their messages, except for negligible failure in schemes that are probabilistic or noisy.

The Challenger must specify the exact attack interface. The same encryption algorithm can be secure in one game and insecure in another.

IND-CPA

In the IND-CPA game, the adversary receives \(pk\) and chooses equal-length messages \(m_0,m_1\). The challenger samples \(b\leftarrow\{0,1\}\) and returns

\[c^*=\mathsf{Enc}_{pk}(m_b).\]

The adversary outputs \(b'\). Its advantage is

\[\operatorname{Adv}^{\mathsf{ind\text{-}cpa}}_\Pi(A) =\left|\Pr[b'=b]-\frac12\right|.\]

For public-key encryption, chosen-plaintext access is implicit: anyone can encrypt under \(pk\).

IND-CPA game between \(\mathcal C\) and \(\mathcal A\)

  1. \(\mathcal C\) runs \((pk,sk)\leftarrow\mathsf{KeyGen}(1^\lambda)\) and sends \(pk\) to \(\mathcal A\).
  2. \(\mathcal A\) may compute encryptions on its own using \(pk\). In the symmetric-key version, \(\mathcal C\) provides an encryption oracle.
  3. \(\mathcal A\) submits two equal-length messages \((m_0,m_1)\).
  4. \(\mathcal C\) samples \(b\leftarrow\{0,1\}\) and returns \(c^*=\mathsf{Enc}_{pk}(m_b)\).
  5. \(\mathcal A\) may continue any allowed chosen-plaintext activity.
  6. \(\mathcal A\) outputs \(b'\) and wins if \(b'=b\).

The equal-length condition prevents the ciphertext length from revealing the challenge bit.

IND-CCA1 and IND-CCA2

Challenger \(\mathcal C\)
Adversary \(\mathcal A\)
\((pk,sk)\leftarrow\mathsf{KeyGen}(1^\lambda)\)
\(pk\)
\((m_0,m_1,\mathsf{st})\leftarrow\mathcal A_1(pk),\quad |m_0|=|m_1|\)
\((m_0,m_1)\)
\(b\leftarrow\{0,1\},\quad c^*\leftarrow\mathsf{Enc}_{pk}(m_b)\)
\(c^*\)
\(b^{\prime}\leftarrow\mathcal A_2(\mathsf{st},c^*)\)
\(b^{\prime}\)
\(\mathsf{IND\text{-}CPA}^{\mathcal A}_{\Pi}(1^\lambda):=\mathbf 1[b^{\prime}=b]\)

Chosen-ciphertext security adds a decryption oracle. The challenge ciphertext is excluded, otherwise the game is trivial.

Notion Decryption access
IND-CCA1 Before the challenge only.
IND-CCA2 Before and after the challenge, except for \(c^*\).

IND-CCA2 is the modern hostile-network notion. The adversary may see a challenge ciphertext, modify it, and ask for decryptions of related ciphertexts.

IND-CCA2 game between \(\mathcal C\) and \(\mathcal A\)

  1. \(\mathcal C\) runs \((pk,sk)\leftarrow\mathsf{KeyGen}(1^\lambda)\) and sends \(pk\) to \(\mathcal A\).
  2. \(\mathcal A\) may query a decryption oracle \(O_{\mathsf{Dec}}(c)=\mathsf{Dec}_{sk}(c)\) before the challenge.
  3. \(\mathcal A\) submits equal-length messages \((m_0,m_1)\).
  4. \(\mathcal C\) samples \(b\leftarrow\{0,1\}\) and returns \(c^*=\mathsf{Enc}_{pk}(m_b)\).
  5. \(\mathcal A\) continues to query \(O_{\mathsf{Dec}}\), but the query \(c=c^*\) is forbidden. The Challenger rejects or aborts if the forbidden query is made, depending on the formal convention.
  6. \(\mathcal A\) outputs \(b'\) and wins if \(b'=b\).

IND-CCA1 is the same game except step 5 is removed: no decryption queries are allowed after the challenge.

Challenger \(\mathcal C\)
Adversary \(\mathcal A\)
\((pk,sk)\leftarrow\mathsf{KeyGen}(1^\lambda),\quad \mathcal O_{\mathsf{Dec}}(c):=\mathsf{Dec}_{sk}(c)\)
\((pk,\mathcal O_{\mathsf{Dec}})\)
\(c_i\leftarrow\mathcal A_1^{\mathcal O_{\mathsf{Dec}}}(pk,\mathsf T_{i-1})\)
\(c_i\)
\(m_i:=\mathcal O_{\mathsf{Dec}}(c_i),\quad \mathsf T_i:=\mathsf T_{i-1}\cup\{(c_i,m_i)\}\)
\(m_i\)
\((m_0,m_1,\mathsf{st})\leftarrow\mathcal A_2^{\mathcal O_{\mathsf{Dec}}}(pk,\mathsf T_q),\quad |m_0|=|m_1|\)
\((m_0,m_1)\)
\(b\leftarrow\{0,1\},\quad c^*\leftarrow\mathsf{Enc}_{pk}(m_b)\)
\(c^*\)
\(c_j\leftarrow\mathcal A_3^{\mathcal O_{\mathsf{Dec}}}(\mathsf{st},c^*),\quad c_j\ne c^*\)
\(c_j\ne c^*\)
\(m_j:=\mathcal O_{\mathsf{Dec}}(c_j)\)
\(m_j\)
\(b^{\prime}\leftarrow\mathcal A_4(\mathsf{st},c^*,\mathsf T)\)
\(b^{\prime}\)
\(\mathsf{IND\text{-}CCA2}^{\mathcal A}_{\Pi}(1^\lambda):=\mathbf 1[b^{\prime}=b]\)

Malleability kills CCA security

ElGamal encryption has the form

\[(c_1,c_2)=(g^r,mh^r).\]

From a ciphertext for \(m\), anyone can choose a public group element \(\alpha\) and form \((c_1,\alpha c_2)\), which decrypts to \(\alpha m\) in the message group. This does not automatically violate IND-CPA, but it gives exactly the kind of related-ciphertext behavior that CCA definitions are designed to rule out.

Nonce-based symmetric encryption

For stream-style encryption

\[\mathsf{Enc}_K(N,M)=N\,\|\,(M\oplus F_K(N)),\]

an IND-CPA proof replaces \(F_K\) by a random function. If the challenge nonce is fresh, the mask is a fresh one-time pad.

The theorem has a condition:

\[\operatorname{Adv}^{\mathsf{ind\text{-}cpa}}_\Pi(A) \le \operatorname{Adv}^{\mathsf{prf}}_F(B)+\Pr[\mathsf{nonce\ repeat}].\]

If the same nonce is reused, then

\[C_1\oplus C_2=M_1\oplus M_2.\]

The proof has not failed; the implementation has left the theorem’s hypothesis.

Confidentiality is not authenticity

IND-CPA does not stop ciphertext modification. IND-CCA resists decryption-oracle abuse, but authenticated encryption usually packages confidentiality and ciphertext integrity into a single symmetric primitive. A theorem must say which property is being proved; it should not be inferred from the word “encrypted”.