A modification of the Blum-Micali construction

Question

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.

Answer 1

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

Knowledge of the trapdoor secret would allow the receiver of a message encrypted with the pseudo random one time pad to recover the seed $x$ if one block of the generator output would be xored with a fixed value known to both the sender and receiver.

This would allow to encrypt more than one message by using a random seed for each message. If the seed could not be recovered from the ciphertext then sender and receiver had to securely exchange random seed values for each message in order to avoid using the same pseudo random one time pad twice.