Theorem 6.1 — Polylogarithmic rank gap for supplied primes
ProvedGenericGroupWE.Main.theorem_6_1complexity-theorycryptographygeneric-groupsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
For every , there is a deterministic polynomial-time witness-preserving rank reduction. From a Boolean circuit it first computes a matrix order , independently of the prime. Given any supplied prime , it returns an ordered linearly independent basis of a matrix space over . Every satisfying witness efficiently yields coefficients and factors with
If is unsatisfiable, every nonzero basis combination has rank at least . Order, basis and conversion have polynomial Turing bounds in the encoded instance and , with exponents permitted to depend on . In addition .
Differences from the source:
- generalization: Theorem 6.1 states m=poly(|phi|) → the conclusion also includes |phi|<=m; reason: the proof pads N to at least the encoded input length and equation (33) gives m>N, as required in §7
- generalization: ordinary acyclic Boolean circuit instances → the published raw circuit evaluator, with missing or forward references reading zero; reason: ordinary circuits are included; total evaluation is still compiled gate by gate without any fan-out restriction
- encoding: polynomial-time algorithms on encoded data → a single CookLevin polynomial-step implementation for each length-faithful encoded map; reason: the time predicate bounds actual Turing steps; clocks also bound rounds and state length
- encoding: the basis map is specified for primes p>=2^m, witness conversion for satisfying witnesses, and m=poly(|phi|) → total order, basis and witness maps with unary order output, unconstrained outside those promises except for being well-formed bundles and certificates; reason: an implementation can test the promise in polynomial time and return the empty basis or the zero certificate otherwise, so no source instance changes; unary output of a polynomial-time map is exactly m=poly(|phi|)
Preamble
import Definitions.Def_GenericGroupWE_Main_Reductions
Formal statement
namespace GenericGroupWE.Main
theorem theorem_6_1 :
∀ c : ℝ, 0 < c → ∃ r : RankReduction MIPRE.SAT.Circuit,
r.PolyTime circuitBits ∧
∀ C : MIPRE.SAT.Circuit, (circuitBits C).length ≤ r.order C ∧
∀ p : PrimeOrder, 2^(r.order C) ≤ p.val →
LinearIndependent (ZMod p.val) (r.basis C p).matrices ∧
(∀ w : Bits, SatisfiesCircuit C w → (r.witness C p w).Valid) ∧
((¬ ∃ w : Bits, SatisfiesCircuit C w) →
∀ a : Fin (r.basis C p).k → ZMod p.val,
(r.basis C p).combination a ≠ 0 →
(Real.logb 2 (r.order C : ℝ))^c ≤ ((r.basis C p).combination a).rank) := 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, Theorem 6.1, PDF p. 24 (printed p. 23).
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.