Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.1 — Generic-group witness encryption

Proved
GenericGroupWE.Main.theorem_1_1

by mikedeng1 · Nov 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorycryptographygeneric-groupsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1

For every real constant c>0c>0c>0 and every polynomial-time decidable, polynomially balanced relation V(φ,w)V(\varphi,w)V(φ,w) on bit strings, there exist probabilistic polynomial-time oracle encryption and decryption algorithms. Put n=max⁡(2,λ,∣φ∣)n=\max(2,\lambda,|\varphi|)n=max(2,λ,∣φ∣). For every security parameter λ\lambdaλ, every statement φ\varphiφ, every valid witness www, and either bit β\betaβ,

Pr⁡[Dec(1λ,φ,w,Enc(1λ,φ,β))=β]≥1−2−n.\Pr[\mathrm{Dec}(1^\lambda,\varphi,w,\mathrm{Enc}(1^\lambda,\varphi,\beta))=\beta]\ge1-2^{-n}.Pr[Dec(1λ,φ,w,Enc(1λ,φ,β))=β]≥1−2−n.

For every false statement and every classical adversary making at most n(log⁡2n)cn^{(\log_2n)^c}n(log2​n)c oracle queries,

Adv⁡A≤n−(log⁡2n)c.\operatorname{Adv}_A\le n^{-(\log_2n)^c}.AdvA​≤n−(log2​n)c.

All fresh encodings and algorithm coins, including aborts, are included. The adversary receives the entire public ciphertext, may use arbitrary advice independent of fresh encodings and encryption coins, and may query guessed strings with unbounded local computation. The bounds hold on every input without an asymptotic threshold, and no rank-gap reduction, prime test or compiler is assumed.

Differences from the source:

  • encoding: probabilistic polynomial-time oracle algorithms and bit-or-failure output → bit-string transitions with CookLevin step bounds, polynomial round clocks and state caps; singleton outputs decode to bits and every other output to failure; reason: this is a concrete bounded machine representation, and every other decryption output counts as failure
  • encoding: the exposed-encoding generic adversary → a PMF of bounded-depth adaptive query trees selected from the entire public ciphertext; reason: all queries including invalid guesses count and the encoding table is available only through the same oracle used by decryption
Preamble
import Mathlib
import Definitions.Def_CookLevin_Complexity
import Definitions.Def_GenericGroupWE_Main_Oracle
Formal statement
namespace GenericGroupWE.Main

/-- Hair--Sahai, Witness Encryption via Prime-Order Generic Groups, submission 47,
Theorem 1.1, PDF 2 (printed 1), with §2's exposed-encoding oracle.
Both clocks and state lengths are polynomially capped, and each local transition
has the published Turing-machine step bound. No compiler or rank-gap hypothesis. -/
theorem theorem_1_1 :
    ∀ c : ℝ, 0 < c →
    ∀ (V : Bits → Bits → Bool) (witnessCoefficient witnessDegree : ℕ),
      CookLevin.IsNPVerifier witnessCoefficient witnessDegree V →
      ∃ enc dec : OracleProgram,
        CookLevin.IsPolyTimeComputable enc.next ∧
        CookLevin.IsPolyTimeComputable dec.next ∧
        ∀ (security : ℕ) (statement : Bits),
          (∀ witness : Bits, V statement witness = true → ∀ message : Bool,
            1 - (2 : ℝ) ^ (-(effectiveSize security statement : ℝ)) ≤
              correctnessProbability enc dec security statement witness message) ∧
          ((¬ ∃ witness : Bits, V statement witness = true) →
            ∀ q : ℕ,
              (q : ℝ) ≤ (effectiveSize security statement : ℝ) ^
                ((Real.logb 2 (effectiveSize security statement : ℝ)) ^ c) →
              ∀ A : Adversary q,
                advantage enc security statement A ≤
                  (effectiveSize security statement : ℝ) ^
                    (-((Real.logb 2 (effectiveSize security statement : ℝ)) ^ c))) := 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 1.1, PDF p. 2 (printed p. 1).
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me