Polynomial-time closure of the explicit inversion checker
ProvedHILL.PRG.inversion_checker_polytimeLet 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:
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.
import Definitions.Def_HILL_PRG_InversionCheck
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