§8 CCA Security

CCA Indistinguishability experiment $\operatorname{PrivK}_{\mathscr{A}, \Pi}^{\mathrm{cca}}(n)$

1. A key $k$ is generated by running $Gen(1^n)$.

2. Adversary $\mathscr A$ is given input $1^n$ and oracle access to $Enc_k ( \cdot )$ and $Dec_k ( \cdot )$.

   Adversary outputs a pair of messages $m_0, m_1$ of the same length.

3. A uniform bit $b \leftarrow \{0,1\}$ is chosen, the challenge ciphertext $c \leftarrow Enc_k (m_b)$ is computed and given to $\mathscr A$.

4. Adversary continues to have oracle access to $Enc_k ( \cdot )$ and $Dec_k ( \cdot )$ , but is not allowed to query $Dec_k ( \cdot )$ on the challenge ciphertext $c$ itself. Adversary then outputs a bit $b'$.

5. Adversary succeeds and the output of the experiment is defined to be $1$ if $b' = b$ and $0$ otherwise.

CCA Security: Definition

• Definition. A private-key encryption scheme $\Pi$ has indistinguishable encryptions under a chosen-ciphertext attack, or is CCA-secure, if for all probabilistic polynomial-time adversaries $\mathscr A$, there is a negligible function $\epsilon$ such that:

  $$\operatorname{Pr}\left[\operatorname{PrivK}_{\mathscr{A}, \Pi}^{\mathrm{cca}}(n)=1\right] \leq \frac{1}{2}+\epsilon(n)$$

  where the probability is taken over all randomness used in the experiment (to choose $k, b$, and any randomness in $Enc_k ( \cdot )$).

CCA-Security: Multiple Encryptions

• Theorem. If a private-key encryption scheme $\Pi$ has indistinguishable encryptions under a chosen-ciphertext attack (i.e., is CCA-secure) then it has indistinguishable multiple encryptions under a chosen-ciphertext attack, i.e., is also CCA-secure under multiple encryptions.

CCA-Security and Malleability

• Malleability: A scheme is malleable if it is possible to modify a ciphertext (from $c$ to $c'$) and thereby cause a predictable change to the plaintext.
• Lemma: No malleable scheme can be CCA-secure.

— Feb 17, 2023

§8 CCA Security by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.