Lemma 3.4 — Fixed linear tests
ProvedGenericGroupWE.Main.lemma_3_4complexity-theorycryptographygeneric-groupsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let , let be prime, and let be linearly independent matrices over . Suppose every nonzero combination has rank at least the real number . Fix coefficients before the random encryption coordinates are sampled. The exact conditional encryption law satisfies
for every nonzero coefficient vector and either bit. For message one the bound improves to . The zero coefficient vector gives probability one for either bit.
Differences from the source:
- generalization: a false SAT instance, its rank-gap basis, and a supplied prime p>=2^m → any linearly independent matrix family with the same rank lower bound, and p>=m; reason: the proof uses only rank, basis independence and the distinct residues 1,...,m
- encoding: finite indexed families, prime-field residues, and an encoded group equality test → Fin-indexed ZMod families and the corresponding scalar equality to zero; reason: zero-based finite carriers preserve the instances, and injectivity of every encoding makes the scalar and group equality events identical, so averaging over the encoding is redundant for this test
Preamble
import Definitions.Def_GenericGroupWE_Main_Scheme
Formal statement
namespace GenericGroupWE.Main
open scoped BigOperators
theorem lemma_3_4 (m : ℕ) (hm : 0 < m) (p : PrimeOrder) (B : MatrixBundle m p)
(hp : m ≤ p.val)
(hlin : LinearIndependent (ZMod p.val) B.matrices) (R : ℝ)
(hrank : ∀ a : Fin B.k → ZMod p.val, B.combination a ≠ 0 →
R ≤ (B.combination a).rank)
(α : ZMod p.val) (β : Fin m → ZMod p.val) (γ : Fin B.k → ZMod p.val) :
((α = 0 ∧ β = 0 ∧ γ = 0) → ∀ message,
fixedTestProbability B hm α β γ message = 1) ∧
((¬ (α = 0 ∧ β = 0 ∧ γ = 0)) →
(∀ message, fixedTestProbability B hm α β γ message ≤
(m : ℝ)^(-R) + (p.val : ℝ)⁻¹) ∧
fixedTestProbability B hm α β γ true ≤ (p.val : ℝ)⁻¹) := 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 3.4, PDF p. 9 (printed p. 8).
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.