Proof of Theorem 6.3 — PRG existence implies OWF existence
ProvedHILL.PRG.prg_implies_owfcryptographyhillone-way-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pseudorandom-generator
If a polynomial-time pseudorandom generator exists, then a polynomial-time one-way function exists:
This is the direction cited to Levin in the proof of Theorem 6.3. It is an existential claim: the source generator itself need not be one-way if it stretches by only one bit.
Formalization Note Both primitives use uniform adversaries and qualitative negligible success. The paper attributes this direction to [Levin87] without a separate numbered result; the quantitative reduction is outside scope.
Preamble
import Mathlib import Definitions.Def_HILL_PRG_Model
Formal statement
namespace HILL.PRG
/-- The Levin87 direction cited in the proof of Theorem 6.3, p. 1387. -/
theorem prg_implies_owf :
(∃ G : FunEns, IsPRG G (fun _ => 0)) →
∃ F : FunEns, IsOWF F := by sorry
end HILL.PRG
Source
Håstad, Impagliazzo, Levin and Luby, A pseudorandom generator from any one-way function, SIAM J. Comput. 28(4), 1999, p. 1387, proof of Theorem 6.3 (first direction)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.