Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§6.2, p. 21 — the polynomial found in Step 3 of Rec\mathsf{Rec}Rec is unique

Proved
FuzzyExtractors.ImprovedJS.pLow_unique

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polynomialsreed-solomonsecure-sketch

Let F\mathcal FF be a field, t≤st\le st≤s natural numbers, w′⊆Fw'\subseteq\mathcal Fw′⊆F with ∣w′∣=s|w'|=s∣w′∣=s, and b:F→Fb:\mathcal F\to\mathcal Fb:F→F any assignment of target values. If p1,p2∈F[z]p_1,p_2\in\mathcal F[z]p1​,p2​∈F[z] both have degree at most s−t−1s-t-1s−t−1 and each satisfies pj(x)=b(x)p_j(x)=b(x)pj​(x)=b(x) for at least s−t/2s-t/2s−t/2 points x∈w′x\in w'x∈w′, then

p1=p2.p_1 = p_2.p1​=p2​.

This is the uniqueness half of the decoding step: the polynomial plowp_{\mathrm{low}}plow​ that Rec\mathsf{Rec}Rec looks for in Step 3 of Construction 5 is determined by its input.

Formalization Note. The paper's sentence reads "no two distinct polynomials of degree s−t−1s-t-1s−t−1 can get the correct bib_ibi​ on more than s−t/2s-t/2s−t/2 aia_iai​s"; the argument it gives ("else, they agree on at least s−ts-ts−t points") and the use in Step 3 need at least s−t/2s-t/2s−t/2, which is what is stated here. "At least s−t/2s-t/2s−t/2" is doubled to 2⋅#≥2s−t2\cdot\#\ge 2s-t2⋅#≥2s−t, and "degree at most s−t−1s-t-1s−t−1" is degree < s - t. The target values bbb are arbitrary (in the application b=phighb=p_{\mathrm{high}}b=phigh​). The paper leaves t≤st\le st≤s implicit; it is a hypothesis here.

Preamble
import Mathlib
import Definitions.Def_FuzzyExtractors_ImprovedJS_Basic
open Polynomial
Formal statement
namespace FuzzyExtractors.ImprovedJS

/-- Construction 5 analysis (p. 21): two polynomials of degree at most s − t − 1 that each agree
with prescribed values b on at least s − t/2 points of an s-element set w′ (doubled:
2·#agreements ≥ 2s − t) are equal. -/
theorem pLow_unique {𝔽 : Type} [Field 𝔽] [DecidableEq 𝔽] (s t : ℕ) (hts : t ≤ s)
    (w' : Finset 𝔽) (hw' : w'.card = s) (b : 𝔽 → 𝔽) (p₁ p₂ : 𝔽[X])
    (hdeg₁ : p₁.degree < ((s - t : ℕ) : WithBot ℕ))
    (hdeg₂ : p₂.degree < ((s - t : ℕ) : WithBot ℕ))
    (hagree₁ : 2 * s - t ≤ 2 * (w'.filter fun x => p₁.eval x = b x).card)
    (hagree₂ : 2 * s - t ≤ 2 * (w'.filter fun x => p₂.eval x = b x).card) :
    p₁ = p₂ := by sorry

end FuzzyExtractors.ImprovedJS
Source
Dodis, Ostrovsky, Reyzin & Smith, Fuzzy Extractors, arXiv:cs/0602007v4, §6.2, analysis of Construction 5, p. 21, "That polynomial is unique, since no two distinct polynomials of degree s−t−1 …"
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

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