Efficient Amplification of the Security of Weak Pseudo-Random Function Generators

摘要

We show that given a PRFG (pseudo-random function generator) G that is (1~c)-partially secure there exists a polynomial p such that the construction g_1 (x⊕r_1)⊕...⊕g_(p(n)) (x ⊕r_p(n)) produces a strongly secure PRFG, where g_i ∈ G and r_i are strings of random bits, and the key for the new PRFG is c omposed of the n 's and keys for the g_i's. This is the first "natural" construction of a (totally secure) PRFG from a partially secure PRFG. Using results of Luby and Rackoff, this result also demonstrates how to construct a PRPG "naturally" from a partially secure PRPG.