Lemma 5.2 — Geometric column combinations span
ProvedGenericGroupWE.Main.lemma_5_2complexity-theorycryptographygeneric-groupsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be prime and let span a nonzero finite-dimensional space of dimension . For , put . There is a nonzero scalar polynomial such that
This is the geometric spanning family used to select a sample of the weighted stack.
Differences from the source:
- encoding: finite indexed families and field residues → Fin-indexed families and ZMod prime fields; reason: zero-based indices and explicit finite carriers change no mathematical instance
Preamble
import Mathlib
Formal statement
namespace GenericGroupWE.Main
open scoped BigOperators
theorem lemma_5_2 (p N : ℕ) [Fact p.Prime] (hp : 2^N < p)
(V : Type*) [AddCommGroup V] [Module (ZMod p) V] [FiniteDimensional (ZMod p) V]
(c : Fin (N + 1) → V)
(hpos : 0 < Module.finrank (ZMod p) (Submodule.span (ZMod p) (Set.range c))) :
let ρ := Module.finrank (ZMod p) (Submodule.span (ZMod p) (Set.range c))
∃ Δ : Polynomial (ZMod p), Δ ≠ 0 ∧ Δ.natDegree ≤ N * ρ ∧
∀ t : ZMod p, Δ.eval t ≠ 0 →
let ds := fun j : Fin ρ => ∑ i : Fin (N+1),
((((2 : ZMod p)^j.val) * t)^i.val) • c i
LinearIndependent (ZMod p) ds ∧
Submodule.span (ZMod p) (Set.range ds) = Submodule.span (ZMod p) (Set.range c) := by sorry
end GenericGroupWE.Main
Source
Hair and Sahai, Witness Encryption via Prime-Order Generic Groups, STOC 2027 submission #47 (PDF built 2026-11-02; SHA-256 0b7f14e2db9bb3e199883ab907f854b7b5884c7c9f3d1e4c306bb71e89b659cb), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/47.pdf, Lemma 5.2, PDF p. 17 (printed p. 16).
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.