Theorem 3.1 — Witness encryption from bounded-factor MinRank
ProvedGenericGroupWE.Main.theorem_3_1Let . Suppose a deterministic polynomial-time witness-preserving reduction computes and, for every supplied prime , an ordered linearly independent matrix basis. Valid witnesses efficiently produce a nonzero rank-one combination with Boolean right factor; on false statements every nonzero combination has rank at least the real number . Assume and uniformly over instances. There are polynomial-time oracle encryption and decryption algorithms, using the supplied prime, with correctness at least on every instance and witness. For all sufficiently large ,
on every false statement, for every generic adversary of that query budget. Only security has a sufficiently-large threshold.
Differences from the source:
- reading: m=poly(n) and R log n=o(m) although m also depends on lambda and phi → one uniform polynomial bound and an epsilon threshold valid for every instance of effective size at least that threshold; reason: this is the uniform reading needed by the pointwise guarantee and the application 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
- generalization: the theorem sentence gives p to encryption as a public input, and (1) obtains a group of that order → an added conclusion that every non-abort ciphertext carries a group context of order exactly p; reason: this is the first step of the construction and ties the existential algorithms to the supplied prime; dropping the clause gives the source claim
import Definitions.Def_GenericGroupWE_Main_Reductions
namespace GenericGroupWE.Main
theorem theorem_3_1
(r : RankReduction (ℕ × MIPRE.SAT.Circuit))
(htime : r.PolyTimeOn circuitInstanceBits
(fun i p => 2^(r.order i) ≤ p.val ∧ p.val < 2^(r.order i+1))
(fun i w => SatisfiesCircuit i.2 w))
(R : ℕ → ℝ)
(hsize : ∀ i, 16 * circuitInstanceSize i ≤ r.order i)
(hpoly : ∃ C d : ℕ, ∀ i, r.order i ≤ C * (circuitInstanceSize i + 1)^d)
(hbasis : ∀ (i : ℕ × MIPRE.SAT.Circuit) (p : PrimeOrder),
2^(r.order i) ≤ p.val → p.val < 2^(r.order i+1) →
LinearIndependent (ZMod p.val) (r.basis i p).matrices ∧
(∀ w, SatisfiesCircuit i.2 w → (r.witness i p w).Valid) ∧
((¬ ∃ w, SatisfiesCircuit i.2 w) → ∀ a,
(r.basis i p).combination a ≠ 0 →
R (circuitInstanceSize i) ≤ ((r.basis i p).combination a).rank))
(hdiverges : ∀ B : ℝ, ∃ threshold : ℕ, ∀ n : ℕ, threshold ≤ n → B ≤ R n)
(hlittleo : ∀ ε : ℝ, 0 < ε → ∃ threshold : ℕ,
∀ i : ℕ × MIPRE.SAT.Circuit, threshold ≤ circuitInstanceSize i →
R (circuitInstanceSize i) * Real.logb 2 (circuitInstanceSize i : ℝ) ≤ ε * r.order i) :
∃ enc dec : OracleProgram,
CookLevin.IsPolyTimeComputable enc.next ∧ CookLevin.IsPolyTimeComputable dec.next ∧
(∀ (i : ℕ × MIPRE.SAT.Circuit) (p : PrimeOrder),
2^(r.order i) ≤ p.val → p.val < 2^(r.order i+1) →
(∀ message : Bool, ∀ ciphertext ∈ (suppliedEncryption enc i.1 i.2 p message).support,
ciphertext.output.isSome → ∃ Γ, ciphertext.context = some Γ ∧ Γ.p = p.val) ∧
∀ w, SatisfiesCircuit i.2 w → ∀ message,
1 - (2 : ℝ)^(-(circuitInstanceSize i : ℝ)) ≤ suppliedCorrectness enc dec i.1 i.2 p w message) ∧
(∃ threshold : ℕ, ∀ (i : ℕ × MIPRE.SAT.Circuit), threshold ≤ circuitInstanceSize i →
(¬ ∃ w, SatisfiesCircuit i.2 w) → ∀ p : PrimeOrder,
2^(r.order i) ≤ p.val → p.val < 2^(r.order i+1) →
∀ Q : ℕ, (Q : ℝ) ≤ (circuitInstanceSize i : ℝ)^(R (circuitInstanceSize i)/8) →
∀ A : Adversary Q, suppliedAdvantage enc i.1 i.2 p A ≤
(circuitInstanceSize i : ℝ)^(-(R (circuitInstanceSize i)/8))) := by sorry
end GenericGroupWE.Main
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.