Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Polynomial-time closure of the explicit inversion checker

Proved
HILL.PRG.inversion_checker_polytime

by Victorized · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexitycryptographyhillturing-machine

Let T,L,E,IT,L,E,IT,L,E,I be total polynomial-time functions on bit strings. They serve as unary length programs, an evaluator, and an inverter. Then the explicit inversion-checking program built from them is polynomial time:

T,L,E,I∈FP⟹Check⁡(T,L,E,I)∈FP.T,L,E,I\in\mathrm{FP}\quad\Longrightarrow\quad \operatorname{Check}(T,L,E,I)\in\mathrm{FP}.T,L,E,I∈FP⟹Check(T,L,E,I)∈FP.

The checker reads the unary security parameter, separates the image from the coin suffix using the length program, runs the inverter, checks the candidate seed length, and compares the evaluated image with the target. The function is defined on every bit string, including malformed encodings. This assertion supplies the computational closure step in the reverse implication of the HILL equivalence.

Formalization Note Polynomial time means Mathlib's bundled TM2 machine model with polynomial running-time bounds. This open theorem does not assume cryptographic hardness and does not import the reverse implication.

Formalization credit: Wentao Li (Victor), under the Prove2Me account Victorized, with assistance from OpenAI Codex.

Preamble
import Definitions.Def_HILL_PRG_InversionCheck
Formal statement
namespace HILL.PRG

/-- Polynomial-time closure for the explicit inverter checking program. -/
theorem inversion_checker_polytime (T L E I : Bits → Bits)
    (hT : PolyTimeComputable T) (hL : PolyTimeComputable L)
    (hE : PolyTimeComputable E) (hI : PolyTimeComputable I) :
    PolyTimeComputable (inversionChecker T L E I) := by sorry

end HILL.PRG
Source
Håstad, Impagliazzo, Levin, Luby, A Pseudorandom Generator from Any One-Way Function, SIAM J. Comput. 28(4), 1999, p. 1387, Theorem 6.3, reverse implication attributed to Levin (1987); https://www.cs.bu.edu/fac/lnd/pdf/hill.pdf. The checking algorithm and quantitative counting bound are an explicit formalization of the standard inverter-to-distinguisher reduction.

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