Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
$m_0$ and $m_1$ certainly still have to have the same length. Check Definition 3.8. With messages of different length, the security definition becomes meaningless. –  Maeher May 21 at 8:04

1 Answer 1

up vote 1 down vote accepted

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).

share|improve this answer
In that case, one could repair the reduction by having it only take the length-$\hspace{.02 in}|\hspace{.02 in}M\hspace{.02 in}|$ output from $G$. $\hspace{.67 in}$ –  Ricky Demer May 22 at 23:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.