# If a stream cipher uses a truly random, injective function, can we get rid of epsilon?

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?

• If $G$ is injective function then are there default values on $K'$ that are not set by $G$? Feb 2 at 21:20
• 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. Feb 2 at 21:35
• 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! Feb 2 at 21:45

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$$.