Consider the following modification of the Blum-Micalli construction (denoted by BM):
$G_l(x) = f^l(x) || BM^l(x)$
I am asked the following questions about it:
Show it is a PRG of fixed stretch for every fixed $l$ polynomial in n.
Discuss the advantages/disadvantages of outputting also $f^l(x)$.
In particular, consider the case when a trap door permutation is used for $f$ and the resulting PRG is used within the pseudo random one time pad.
As an advantage I would say that this PRG gives $n$ more bits than plain Blum-Micali construction. However, I'm not sure how to handle the rest of the questions. Could you provide any hints?
Notation
$BM^j(x) = hc(f^{j-1}(x))\| \ldots \| hc(f(x)) \| hc(x)$
where $f: \{0,1\}^* \to \{0,1\}^*$ is a permutation on $\{0,1\}^n$ for every $n$ with hard-core predicate $hc$ and where $f^j$ denotes the composition of $f$ with itself $j$ times.
Solution
In this document you may find an answer as discussed in my class. I will still appreciate the effort to create a publicly available and pedagogic solution to this problem. Once it is here, I will remove the link.
One question that I still have is if the concatenation of unpredicatable functions is unpredictable.