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

Consider 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 semantically 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 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.