Theorem 1.1 — Generic-group witness encryption
ProvedGenericGroupWE.Main.theorem_1_1For every real constant and every polynomial-time decidable, polynomially balanced relation on bit strings, there exist probabilistic polynomial-time oracle encryption and decryption algorithms. Put . For every security parameter , every statement , every valid witness , and either bit ,
For every false statement and every classical adversary making at most oracle queries,
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
import Mathlib import Definitions.Def_CookLevin_Complexity import Definitions.Def_GenericGroupWE_Main_Oracle
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.