Imagine an encryption scheme defined as follows for a fixed $|k|$ and $|m| > |k|$:

  • $K = \{0, 1\}^{|k|}$
  • $K' = M = C = \{0, 1\}^{|m|}$
  • $G: K \rightarrow K'$ is a truly random injective function
  • $E(k, m) = m \oplus G(k)$
  • $D(k, c) = c \oplus G(k)$

Is this construction semantically secure without the epsilon bound? In other words, is it the case that, in the semantic security game, the probability that the adversary guesses correctly which ciphertext they've been given is exactly $\frac{1}{2}$?

I'm trying to get an intuition for where the epsilon requirement comes from, and my guess is that it's required since, for real stream ciphers, $G$ is not necessarily injective, and so given a particular $c, m_0, m_1$, it could be the case that there are more keys, $k$, such that $E(k, m_0) = c$ than such that $E(k, m_1) = c$. Is understanding correct?

  • $\begingroup$ If $G$ is injective function then are there default values on $K'$ that are not set by $G$? $\endgroup$
    – kelalaka
    Feb 2 at 21:20
  • $\begingroup$ Not sure what you mean by "default values"? Maybe this is what you're asking about: Since $|K'| > |K|$, there are values in $K'$ that have no pre-image in $K$ under $G$. But that's true even if $G$ isn't injective. $\endgroup$
    – joshlf
    Feb 2 at 21:35
  • $\begingroup$ I understand the first two steps as defining the spaces, not random assignment. How is $K$ sampled and what are the non-mapped values of $K'$. This missing information makes this Q unanswerable for me! $\endgroup$
    – kelalaka
    Feb 2 at 21:45

1 Answer 1


Is understanding correct?

No, it comes from the requirement that $|m| > |k|$.

Consider this adversary: he picks a random key $k'$. Then, when he gets the plaintext/ciphertext pair $m, c$, he checks whether $m \oplus G(k') = c$.

If the ciphertext was generated by the encryptor, this will be true with probability $1 / |k|$ (and making $G$ injective makes this exact, rather than a lower bound); if it was generated by a random source, this will be true with probability $1 / |m|$.

Because $1 / |k| > 1 / |m|$, this means that this (rather simple-minded) distinguisher does have a small advantage, hence the $\epsilon$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.