Prefix property for variable length pseudo-random generators I'm currently working through Katz &amp; Lindell's Introduction to Modern Cryptography. In section 3.4.2, they introduce the definition of a variable output-length pseudorandom generator $G$. The definition of $G(s,1^l)$ is such that the output is of length $l$.

Using such a psuedo-random generator, they define a variable-length encryption scheme (here, called $\pi_{VarPRG}$) in the natural manner for variable length messages:


  Encryption: $Enc:\mathcal{K}\times\mathcal{M}\to\mathcal{C}$ where $C=Enc(K,M)=G(K,1^{|M|})\oplus M$
  
  Decryption: Inverse of encryption for the ciphertext length $|C|$.


However, they go on to include the side-condition:


  For all $s$, $l$, $l'$ with $l&lt;l'$, the string $G(s,1^l)$ is a prefix of $G(s,1^{l'})$.


They claim this is a "technicality" of proving indistinguishable encryptions in the presence of an eavesdropper for the variable length encryption scheme defined above. After staring at this for the best part of an hour, I am not fully understanding where this subtlety comes into the proof. (It is, after all, a subtlety.)



My first attempt to gain some insight into the problem:

In the proof of $PrivK^{eav}_{\mathcal{A},\pi_{VarPRG}}(l)$ for the encryption scheme shown above, we suppose $G$ is a secure pseudo-random generator and then suppose, for contradiction, that $\pi_{VarPRG}$ is not secure in the presence of an eavesdropper. In other words, there exists some adversary $\mathcal{A}$ for which 

$Pr(PrivK^{eav}_{\mathcal{A},\pi}(l)=1)\not\leq \frac{1}{2} + negl(l)$

We proceed by using the adversary $\mathcal{A}$ to build a (probabilistic, polynomial-time) distinguisher $\mathcal{D}$ for the variable output-length PRG $G$, and show that this contradicts the assumed pseudo-randomness of $G$.

All well so far. The adversary $\mathcal{A}$ will, when invoked, output two messages $m_0$ and $m_1$, which one assumes can be different lengths ($|m_0|\not=|m_1|$). At this point, I get stuck:

Where does the subtlety, noted above with regard to the prefix property of $G$ for $1^l&lt;1^{l'}$, come into this?
Recall that Katz-Lindell defines a variable output-length pseudorandom generator as a deterministic polynomial time algorithm G with three properties:


Let $s$ a string and $n&gt;0$ an integer. Then $G(s,1^n)$ outputs a string of length $n$
For all $s,n,n'$ with $n&lt;n'$, the string $G(s,1^n)$ is a prefix of $G(s,1^{n'})$
Define $G_{\ell}:=G(s,1^{\ell(|s|)})$. Then for every polynomial $\ell(\cdot)$ it holds that $G_{\ell}$ is a pseudorandom generator with expansion factor $\ell$.


(I have changed some $\ell$s to $n$s to avoid variable collision).

The second condition is necessary because, without it, this definition does not say anything about the output of $G(s,1^n)$ in the case where $|s|&gt;n$. This is because Katz-Lindell defines a pseudorandom generator (on page 70) to have an $\textit{expansion}$ property-- the output of a pseudorandom generator is longer than the seed--so the above property 3 doesn't (by itself) tell us anything about the case where $|s|&gt;n$.

This is a problem because (as defined on page 63) the first step of the eavesdropping indistinguishability experiment is that "The adversary $\mathcal{A}$ is given input $1^n$, and outputs a pair of messages $m_0,m_1$ of the same length."

The seed used in encryption is of length $n$, so the adversary could choose messages of length less than $n$. Then the messages would be encrypted with the output of $G(k,1^{|m_0|})$ which, as mentioned above, is not guaranteed to be pseudorandom without property 2.

However, it is an easy lemma to prove that a truncation of a pseudorandom string is also pseudorandom. This, together with properties 2 and 3, gives us that all outputs of a variable output-length pseudorandom generator are pseudorandom, and the security proof goes through as normal.