Proposition 3.3 — Correctness of decryption
ProvedGenericGroupWE.Main.prop_3_3complexity-theorycryptographygeneric-groupsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let , , and let be prime. For any valid certificate with Boolean, and either encrypted message, the explicit bounded sampler and valid-witness oracle decryption core satisfy
The abort outcome is included; decryption returns zero there, so aborts can be errors for message one. Both inequalities are part of the item.
Differences from the source:
- generalization: a satisfying witness of the source reduction and a prime below 2^(m+1) → any valid rank-one Boolean-right-factor certificate and any prime p>=2^m; reason: correctness needs the certificate and lower prime bound, not the NP label, basis independence, NO-case rank gap or upper prime bound
Preamble
import Definitions.Def_GenericGroupWE_Main_Scheme
Formal statement
namespace GenericGroupWE.Main
open scoped BigOperators
theorem prop_3_3 (n m : ℕ) (hn : 2 ≤ n) (hm : 16*n ≤ m) (p : PrimeOrder)
(hp : 2^m ≤ p.val) (B : MatrixBundle m p) (w : RankOneCertificate B)
(hw : w.Valid) (message : Bool) :
probability (boundedEncryption B n message) (fun C => schemeDecryption w C ≠ some message) ≤
samplingFailure B n + (m : ℝ)^2 * (2 : ℝ)^(-(m : ℝ)) ∧
samplingFailure B n + (m : ℝ)^2 * (2 : ℝ)^(-(m : ℝ)) ≤ (2 : ℝ)^(-(n : ℝ)) := 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, Proposition 3.3, PDF p. 9 (printed p. 8).
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.