Lemma 4.8 — leftover hash lemma
ProvedHILL.PRG.lemma_4_8cryptographyhillone-way-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pseudorandom-generator
Let be a probability distribution on -bit strings with order-two Rényi entropy at least . Let be an integer with , and let be any polynomial-time pairwise-independent universal hash family from bits to bits, with a uniformly random -bit key . If has law and is independent and uniform on bits, then
This is the statistical extraction estimate used when the paper turns entropy into output bits.
Formalization Note Universal hashing uses the exact pairwise-independence identity of Definition 4.6, not a collision-only bound. The finite source law is explicitly nonnegative and normalized. The theorem has no computational hardness premise.
Preamble
import Mathlib import Definitions.Def_HILL_PRG_Model import Definitions.Def_HILL_PRG_Constructions
Formal statement
namespace HILL.PRG
/-- Lemma 4.8, p. 1378: leftover hashing at Rényi entropy m. -/
theorem lemma_4_8 (n m e kl : ℕ) (he : 0 < e) (hme : 2 * e ≤ m)
(D : Bits → ℝ) (hD : IsProbOn (cube n) D)
(hH : (m : ℝ) ≤ renyiOn (cube n) D)
(h : HashFamily) (hh : h.IsUniversal)
(hin : h.inLen n = n) (hout : h.outLen n = m - 2 * e)
(hkey : h.keyLen n = kl) :
statDistOn (cube (m - 2 * e) ×ˢ cube kl)
(hashJoint D h n) (hashUniform h n) ≤
(2 : ℝ) ^ (-((e : ℝ) + 1)) := 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. 1378, Lemma 4.8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.