How should I answer the following problem:

Let $F = F0 \times F1$ be a pseudorandom generator with expansion factor $2n$ such that for all $x \in \{0, 1\}^n$ $$F(x) = (F_0 (x) || F_1 (x))$$ and $$|x| = |F_0 (x)| = |F_1(x)|.$$ Prove that $$F'(x) = (F_0 (F_0 (x)) || F_0 (F_1 (x)) || F_1 (F_0 (x)) || F_1 (F_1 (x)))$$ is a pseudorandom generator with expansion factor $4n.$

Here I am not able to understand how expansion factor changes?

I am more interested in general proof structure for solving similar proofs.

I am beginner so more detailed explanation will be helpful.


The concatenation operator $||$ in e definition $F$ ensures an expansion $n \rightarrow 2n$ since both $F_0$ and $F_1$ map $n$ bits to $n$ bits.

The argument for $F'$ is similar since repeated application of two $n$ bit to $n$ bit functions gives an $n$ bit to $n$ bit function, and four of those are concatenated in $F'$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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