Prefix property for variable length pseudo-random generators

Question

I'm currently working through Katz & 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<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<1^{l'}$, come into this?

Answer 1

Recall that Katz-Lindell defines a variable output-length pseudorandom generator as a deterministic polynomial time algorithm G with three properties:

1. Let $s$ a string and $n>0$ an integer. Then $G(s,1^n)$ outputs a string of length $n$
2. For all $s,n,n'$ with $n<n'$, the string $G(s,1^n)$ is a prefix of $G(s,1^{n'})$
3. 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|>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|>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.

Answer 2

If you work through the reduction proof, I suspect you'll find the reduction doesn't work without that side-condition: the reduction falls apart.

Where does it fail? The goal of the reduction is to show how to use any black box to break the encryption scheme, to also break $G$. The natural reduction works by taking a sufficiently long output from $G$, keep the first $|M|$ bits of it, use it to form a simulated ciphertext $C$, and then feed it to the black box. We want to argue the simulated ciphertext $C$ looks just like a real ciphertext, so the black box will break it. However, if $G$ doesn't satisfy the side-condition, then this particular argument falls apart. If $G$ doesn't satisfy the side-condition, then taking a bunch of output from $G$ and then truncating it to keep the first $|M|$ bits does not yield the same string that real encryption would have used to xor $M$ with, when encrypting $M$.

As far as I know, we could adjust the reduction to avoid this problem, but we might need to check that the definition of $G$ still makes sense. I'm used to thinking of security for a pseudorandom generator in an adversary model where the adversary doesn't get to choose any of the inputs to the pseudorandom generator. If you want to adjust the reduction, then the adversary needs the ability to supply a chosen input to the pseudorandom generator (namely, the length field).