A modification of the Blum-Micalli construction

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:

1. Show it is a PRG of fixed stretch for every fixed $l$ polynomial in n.

2. Discuss the advantages/disadvantages of outputting also $f^l(x)$.

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