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?


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


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.

  • $\begingroup$ What is $f^l(x)$? $\endgroup$ Jan 27, 2019 at 0:47
  • $\begingroup$ @GeoffroyCouteau now the notation is explained, thank you $\endgroup$ Jan 27, 2019 at 9:43
  • $\begingroup$ 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. $\endgroup$
    – tylo
    Nov 23, 2019 at 10:10

1 Answer 1

  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.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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