Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Explicit inversion-checking distinguisher

Definition
HILL_PRG_InversionCheck

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

complexitycryptographyhillpseudorandom-generator

The inversion-checking program receives a security parameter, a target image, and inverter coins. It runs the inverter, verifies the candidate seed length, evaluates the generator at that candidate, and accepts exactly when the computed image equals the target.

The four component programs compute the unary seed length, the unary output length, generator evaluation, and inversion. The image is separated from the random coins using the computed output length. All inputs, including malformed encodings, have a defined output.

Formalization Note This definition specifies the program but does not assert its running-time bound. Polynomial-time closure and correctness are proved separately.

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

Definition code
import Definitions.Def_HILL_PRG_Model

namespace HILL.PRG

/-- Check the output of an inverter, retaining the security parameter and target image.
`T` and `L` compute the unary seed and image lengths, `E` evaluates the generator,
and `I` is the inverter. Malformed inputs are assigned a total, deterministic result. -/
def inversionChecker (T L E I : Bits → Bits) (w : Bits) : Bits :=
  let n := (w.takeWhile id).length
  let payload := w.drop (n + 2)
  let y := payload.take ((L (List.replicate n true)).length)
  let out := I (enc n payload)
  if out.length = (T (List.replicate n true)).length ∧
      E (encAdvice n 0 out) = y then [true] else []

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