I've seen a lot written about how, in the context of public key cryptosystems, these definitions are equivalent. Is the same true of symmetric key cryptosystems? If so, what are the precise statements of the definitions?

My current understanding


Probability distributions $D_0$ and $D_1$ are said to be indistinguishable if:

$\forall A, |P[b \leftarrow \{0, 1\}; d \leftarrow D_b; A(d) = b] - \frac{1}{2}| \leq \epsilon$

(I'm going to ignore the definition of $\epsilon$ here because, IIUC, they're the same in the definition of indistinguishability and of semantic security, and so it's enough to say that it's the same quantity.)

A symmetric cipher is said to be semantically secure if:

$\forall A, \forall m_0, m_1, |P[b \leftarrow \{0, 1\}; k \leftarrow K; A(m_0, m_1, E(k, m_b)) = b] - \frac{1}{2}| \leq \epsilon$


IIUC, we can restate this semantic security definition in terms of indistinguishability: We can define the distribution $C_m$ as the distribution of $E(k, m)$ (treating $m$ as fixed and $k$ as the source of randomness). We say that a cipher is semantically secure if, for all message pairs $m_0, m_1$, $C_{m_0}$ is indistinguishable from $C_{m_1}$.

Am I correct:

  • That these are the correct formalisms (and specifically that this is the correct formalism of semantic security in the symmetric key case)
  • That we can restate semantic security in terms of indistinguishability as described
  • 1
    $\begingroup$ Generally when I see semantic security discussed, it is for the fact that it is hard to compute any non-trivial function $f$ of the plaintext. The fact that this is equivalent to IND-CPA security is a strong motivation for IND-CPA security. $\endgroup$
    – Mark Schultz-Wu
    Feb 6 at 4:35


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.