Proof that pseudo-random generated key is semantically secure

Let $G: \{0,1\}^s \rightarrow \{0,1\}^r$ where $r > s \;$ be a secure pseudo-random generator.

Let $\xi = (E,D)$ a semantically secure cipher whose key space is $\{0,1\}^r$

Let $\xi' = (E',D')$ a cipher whose key space is $\{0,1\}^s$ and such that:

• $E'(k, m) = E(G(k), m)$
• $D'(k,\;c)\; = D(G(k),\;c)$

How can I prove that $\xi'$ is semantically secure?

I guess that I should use the fact that a semantically secure cipher uses a random key, so using a pseudo-random key would add just a negligible advantage for the adversary to guess the key, so the sum of the semantically secure negligible advantage and the pseudo-random key negligible advantage would also be negligible, but I'm not sure how to build a proof.

• The proof is completely standard; not sure how one could help you other than writing it for you... – fkraiem Apr 8 '18 at 9:18
• well, one could at least say if I'm right at my thoughts – Daniel Apr 8 '18 at 17:29

In order to answer that, let's remember the definition of a secure PRG:

Let $$G: k \to \{0, 1\}^n$$ be a PRG. $$G$$ is said to be a secure PRG if and only if $$G(k)$$ is indistinguishable from $$r$$, where $$r$$ is a truly random string from $$\{0, 1\}^n$$

By indistinguishable we mean that no statistical test can differentiate $$G(k)$$, where $$k$$ is chosen at random from the set $$K$$, from a truly random string $$r$$, $$r \in \{0, 1\}^n$$.

That said is easy to see that, if $$G$$ is a secure PRG no adversary can distinguish, with non-negligible advantage, the ciphertexts generated from $$E$$ and $$E'$$. So your idea of proof is correct.

Most of the times this should be enough to prove it... But bellow I present a proof using an Attack Game and an Statistical Test

To help with the actual proof one can define the problem as:

If G is a secure PRG, then $$\xi'$$ is semantically secure.

Then, we can use the contrapositive to prove it:

If $$\xi'$$ is not semantically secure, then G is not a secure PRG.

To prove that, given an adversary $$A$$ that can break the semantic security from $$\xi'$$, we need to be able to build an adversary $$B$$ using $$A$$ that can distinguish $$G(k)$$ from $$r$$, again, where $$r$$ is a truly random string from $$\{0, 1\}^n$$.

So, the way we would do this is by using $$B$$ at the same time as the challenger of $$A$$ and as the statistical test to distinguish $$G(k)$$ from $$r$$.

• $$A$$ would provide $$B$$ two messages $$m_0$$ and $$m_1$$;
• Then $$B$$ would get from his challenger an string $$s$$ that can either be $$G(k)$$ or $$r$$;
• Then $$B$$ encrypts $$m_0$$ using $$E$$ and the string $$s$$ as key (essentially, he is using $$E'$$ when $$s = G(k)$$ and $$E$$ when $$s = r$$).
• Finally, $$B$$ sends the encryption $$c$$ to $$A$$ that answers $$1$$ if he thinks $$c$$ comes from the encryption of $$m_1$$, and $$0$$ otherwise.
• $$B$$ outputs to his challenger whatever is the answer of $$A$$

Note that if $$B$$ answer his challenger with $$0$$, then $$s = G(k)$$; If he answers $$1$$, then $$s = r$$.

Given that $$A$$ can break the semantic security of $$\xi'$$ he would output $$0$$ (guess correctly) whenever $$s = G(k)$$, and as we can see, $$B$$ would also be right by answering that $$s$$ is in fact $$G(k)$$.

This would break the definition of a secure PRG, thus proving that $$G$$ is not secure. $$\square$$

Just for a matter of completude:

What you are asking for is also the idea of turning the OTP practical, where the idea is to use a pseudo-random key instead of a truly random key, so we can use small seeds to generate much larger keys.

I should also note that a cipher who uses a PRG to generate its key can't be called a perfectly secure cipher. That's why the definition of security is stretched so the security property depends on the specific generator. That's where the semantic security definition comes on.