Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 6.3 — PRG existence implies OWF existence

Proved
HILL.PRG.prg_implies_owf

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

cryptographyhillone-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:

(∃G  PRG(G))⟹(∃F  OWF(F)).(\exists G\;\mathrm{PRG}(G))\Longrightarrow(\exists F\;\mathrm{OWF}(F)).(∃GPRG(G))⟹(∃FOWF(F)).

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
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me