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.

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

1 Answer 1


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.


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.