Efficient amplification of the security of weak pseudo-random function generators (Q1402360)

It is known that a proper composition of partially secure pseudo-random function generators (PRFG) can amplify security. It is even known that the existence of a partially secure PRFG implies a totally secure PRFG; however the proof made use of a chain of results and was rather unnatural and inefficient. Here in the paper a direct, natural and efficient construction for generating a PRFG from a partially secure PRFG is given. Also, the approach described in the paper together with previous results of Luby and Rackoff allows one to demonstrate a ``natural'' construction of a pseudo-random permutation generator (PRPG) from a partially secure PRPG. The security of the construction is proved using the Diamond Isolation Lemma, introduced and proved in the paper. The construction and results concerning its security are presented with respect to non-uniform adversaries. However, in the final chapter changes required to make the proof also valid in the uniform model are outlined. Furthermore, some interesting questions and suggestions for future research are given there.