Inversion checking gives at least half the inverter success as distinguishing advantage
ProvedHILL.PRG.inverter_check_advantage_boundcryptographyhillprobabilitypseudorandom-generator
Let map -bit seeds to -bit outputs, with . Let be an inverter and a checker using the same independent random coins. On input an image , the checker accepts exactly when returns a seed of the required length whose image under is . Then
This is the finite probability bound underlying the reverse implication of the HILL equivalence. It requires exact output lengths and the stated checker behavior; polynomial-time construction of the checker is a separate computational obligation.
Formalization credit: Wentao Li (Victor), under the Prove2Me account Victorized, with assistance from OpenAI Codex.
Preamble
import Definitions.Def_HILL_PRG_Model
Formal statement
namespace HILL.PRG
theorem inverter_check_advantage_bound (G : FunEns) (A B : Adv)
(hlen : ∀ n x, x ∈ cube (G.t n) → (G.f 0 n x).length = G.ℓ n)
(hcoins : B.coins = A.coins)
(hcheck : ∀ n y r, y ∈ cube (G.ℓ n) → r ∈ cube (A.coins n) →
(B.run (encAdvice n 0 (y ++ r)) = [true] ↔
let out := A.run (enc n (y ++ r));
out ∈ cube (G.t n) ∧ G.f 0 n out = y))
(n : ℕ) (hstr : G.t n < G.ℓ n) :
invSucc G A n ≤ 2 * advantage B n (fun _ => 0) (G.ℓ n)
(G.law (fun _ => 0) n) (uniformBits (G.ℓ n)) := by sorry
end HILL.PRGSource
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.