§5 CPA Security

The CPA Indistinguishability Experiment $\operatorname{PrivK}_{\mathscr{A}, \Pi}^{\mathrm{cpa}}(n)$

• We consider the CPA indistinguishability experiment $\operatorname{PrivK}_{\mathscr{A}, \Pi}^{\mathrm{cpa}}(n)$ for encryption scheme $\Pi = (Gen, Enc, Dec)$, adversary $\mathscr{A}$, and security parameter $n$.
  1. Generate key $k$ by running $Gen(1^n)$.
  2. Adversary is given input $1^n$ and oracle access to $Enc_k(\cdot)$. Adversary outputs messages $m_0, m_1$ such that $|m_0| = |m_1|$.
  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 $\mathscr A$ continues to have oracle access to $Enc_k(\cdot)$ , and outputs bit $b'$.
  5. Adversary succeeds and experiment is defined to be $1$ if $b' = b$, and $0$ otherwise.

CPA-security: Definition

• Definition. A private-key encryption scheme $\Pi = (Gen, Enc, Dec)$ has indistinguishable encryptions under chosen-plaintext attack, or is CPA-secure, if for all probabilistic poly-time adversaries $\mathscr A$, there is a negligible function $\epsilon$ such that

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

  where the probability is taken over any randomness used by $\mathscr A$, and over all the randomness used in the experiment (for choosing $k, b$, and any randomness used by $Enc$).

CPA-Security: Multiple Encryptions

• Theorem. Any private-key encryption scheme that is CPA-secure is also CPA-secure for multiple encryptions.

— Feb 10, 2023

§5 CPA 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.