Theorem 6.1 — Construction 5 is an average-case secure sketch
ProvedFuzzyExtractors.ImprovedJS.theorem_6_1Let be a finite field with elements, used as the universe , and let be natural numbers. Let be the improved Juels–Sudan sketch (Construction 5): outputs the coefficients of degree down to of , and decodes by Reed–Solomon decoding and root finding. Then for every real , is an average-case
That is:
- (correctness) for all -element sets with , ;
- (security) for all random variables over -element subsets of and (arbitrary auxiliary information) with , one has .
In particular the entropy loss of the scheme is at most , which §6.2 shows to be essentially optimal for .
Formalization Note. The paper leaves implicit; it is a hypothesis here. " is a prime power" is automatic since is a finite field. The storage bound ("storage at most ") holds by construction, since the sketch is a vector in , and is not restated. The running-time clause ("SS() and Rec() run in time polynomial in , and ") is dropped: there is no complexity substrate. Logarithms are base 2, is in the joint form (see the definition module), and the auxiliary variable ranges over an arbitrary type.
import Mathlib import Definitions.Def_FuzzyExtractors_ImprovedJS_Basic
namespace FuzzyExtractors.ImprovedJS
/-- Theorem 6.1 (Analysis of Improved JS), p. 22: over a finite field 𝔽 with n elements and for
t ≤ s, Construction 5 is an average-case (SDif_s(𝔽), m, m − t log n, t)-secure sketch, for every m. -/
theorem theorem_6_1 {𝔽 : Type} [Field 𝔽] [Fintype 𝔽] [DecidableEq 𝔽] (s t : ℕ) (hts : t ≤ s)
(m : ℝ) :
FuzzyExtractors.Hamming.IsAvgSecureSketch (sdifDist (𝓤 := 𝔽) (s := s)) m
(m - t * Real.logb 2 (Fintype.card 𝔽)) t (sketch s t) (recover s t) := by sorry
end FuzzyExtractors.ImprovedJS
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.