OWF ⇒ PRG
A one-way function implies a PRG, via the Goldreich–Levin hard-core predicate.
Construction
Migrated verbatim from PRG § Other results:
OWFs imply PRGs, via the Goldreich-Levin hard-core predicate — HILL99, GL89
Notes
The converse also holds — any PRG is a one-way function, since the seed is a preimage of the output — so OWF PRG. The converse direction is its own hyperedge and is not covered by this page.
class is unstated: neither citing page says which notion of reduction is
meant. The construction is standard and is very likely fully black-box, but
recording that here would add a claim the wiki does not make.
The hypothesis owf is the one-wayness notion defined at
preimage-resistance-one-wayness. That definition is keyed
and implicitly compressing, whereas HILL99 is stated for unkeyed one-way
functions — see the note on Hash functions.