Lecture Notes in Computer Science, 2001, Volume 2045/2001, 358-372, DOI: 10.1007/3-540-44987-6_22

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

Steven Myers

View Related Documents

Abstract

We show that given a PRFG (pseudo-random function generator) G which is $ \frac{1} {c} - $ \frac{1} {c} - partially secure, the construction $ \frac{1} {c} - $ \frac{1} {c} - $ \frac{1} {c} - $ \frac{1} {c} - produces a strongly secure PRFG, where g i G and r i are strings of random bits. Thus we present 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 “naturally” construct a PRPG from partially secure PRPG.

Fulltext Preview

Image of the first page of the fulltext document