# 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)$$

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.

• What is $f^l(x)$? – Geoffroy Couteau Jan 27 '19 at 0:47
• @GeoffroyCouteau now the notation is explained, thank you – Rodrigo Jan 27 '19 at 9:43
• Since you place no restriction on $f(x)$, consider the case $f(x)=x$. Of course that immediately breaks the security. So it is impossible to get any useful general statement for all possible functions. – tylo Nov 23 '19 at 10:10

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