§6.4, eqs. (29)–(30) — Surviving column relations span at most ρ² dimensions
ProvedGenericGroupWE.Main.eq_29_30complexity-theorycryptographygeneric-groupsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
For a nonzero represented stack of rank , fix and stack the columns , where and . Their span has dimension satisfying
For every relation , set . Then for every listed weight and polynomial of degree at most ,
Both the dimension bound and the surviving relation are retained in this item.
Differences from the source:
- generalization: the unsatisfiable low-rank prime-field regime of §6.4 → any field and any nonzero represented stack; reason: the two displayed claims use only the assignment-table identities, so they specialize to every stack in the source regime
- 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 Definitions.Def_GenericGroupWE_Main_Tables
Formal statement
namespace GenericGroupWE.Main
open scoped BigOperators
theorem eq_29_30 (K : Type*) [Field K] (N d : ℕ) (hd : 1 ≤ d)
(coefficients : BooleanAssignment N → K)
(hne : representedStack (d := d) coefficients ≠ 0) :
let A := representedStack (d := d) coefficients
1 ≤ survivingDimension hd A ∧ survivingDimension hd A ≤ A.rank ^ 2 ∧
∀ κ : Option (Fin N) → K,
(∑ i, κ i • survivingColumn hd A i) = 0 →
∀ (h : WeightLabel N d) (f : MvPolynomial (Fin N) K), f.totalDegree + 1 ≤ 2*d →
∑ b, coefficients b * affineBit κ b * stackWeight h b *
MvPolynomial.eval (booleanPoint b) f = 0 := 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, §6.4, eqs. (29)–(30), PDF p. 27 (printed p. 26).
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.