Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.6 — Public-key encryption from marked planting and XOR-MAJ

Open
ExpandingCodes.PolynomialStretch.Supplement.goldreich_pke

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

combinatoricscryptographyinformation-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Fix rational ε,C,s\varepsilon,C,sε,C,s and real δ\deltaδ satisfying (8), with 0<ε<1/1000<\varepsilon<1/1000<ε<1/100. The hidden instance is the Corollary 1.2 construction at parameter ε/4\varepsilon/4ε/4: ttt is the specified shared-input count, ℓ=(arity⁡(ε/4)+t)/2\ell=(\operatorname{arity}(\varepsilon/4)+t)/2ℓ=(arity(ε/4)+t)/2, m(n)=rowCount⁡(dimension⁡(ε/4),n−t)m(n)=\operatorname{rowCount}(\operatorname{dimension}(\varepsilon/4),n-t)m(n)=rowCount(dimension(ε/4),n−t) and β=2ℓ−s\beta=2\ell-sβ=2ℓ−s. Assume marked Conjecture 3.1 for these values and Conjecture 3.5 for the random marked XOR-MAJ background. The latter hypothesis retains its vanishing maximal advantage.

There exist a semantically secure bit public-key encryption scheme with actual polynomial-time implementations of all its algorithms, fixed polynomial bounds, and a constant δ′>0\delta'>0δ′>0 such that, for all sufficiently large nnn,

Pr⁡[Decsk(Encpk(b))≠b]≤e−nδ′(b∈{0,1}),\Pr[\mathrm{Dec}_{\mathrm{sk}}(\mathrm{Enc}_{\mathrm{pk}}(b))\ne b]\le e^{-n^{\delta'}}\quad(b\in\{0,1\}),Pr[Decsk​(Encpk​(b))=b]≤e−nδ′(b∈{0,1}), Adv⁡E,n(T)≤e−nδ′for every ∣T∣≤enδ′.\operatorname{Adv}_{E,n}(T)\le e^{-n^{\delta'}}\quad\text{for every }|T|\le e^{n^{\delta'}}.AdvE,n​(T)≤e−nδ′for every ∣T∣≤enδ′.

The circuit sees the whole public key and ciphertext; decryption failures count as errors. The eventual threshold is uniform over the bits and adversary circuits.

This is the second conditional encryption companion theorem, independent of the proof of the code-construction goal. It concludes existence in the generic scheme syntax, rather than assuming a correct or efficient Goldreich scheme as input.

Differences from the source:

  • encoding: polynomial-time public-key encryption and nonuniform circuits → finite transition-table implementations, uniform finite coins, and injective fixed-length public-key/ciphertext slots; reason: makes the computational and probability conventions explicit without imposing an efficiency or security premise
  • encoding: the section fixes admissible rational constants before all asymptotic limits → universal rational parameter binders with computed construction parameters and explicit conjecture predicates; reason: states the complete section hypotheses and ensures one admissible conjecture instance suffices
Preamble
import Definitions.Def_ExpandingCodes_PolynomialStretch_Supplement_Conjectures
set_option autoImplicit false
Formal statement
namespace ExpandingCodes.PolynomialStretch.Supplement

/-- Theorem 3.6: marked planting and random XOR-MAJ at the Corollary 1.2 parameters. -/
theorem goldreich_pke (ε C s : ℚ) (δ : ℝ)
    (hparams : GoldreichParameters ε C s δ)
    (hplant : MarkedPlanting (ε : ℝ) (majorityArity (ε : ℝ))
      (goldreichRows (ε : ℝ)) C ((2 * majorityArity (ε : ℝ) : ℚ) - s) δ)
    (hgoldreich : RandomGoldreich (majorityArity (ε : ℝ))
      C ((2 * majorityArity (ε : ℝ) : ℚ) - s) δ) :
    SecurePKEExists := by sorry

end ExpandingCodes.PolynomialStretch.Supplement
Source
Isaac M Hair, Amit Sahai, Expanding Codes with Polynomial Stretch, STOC 2027 submission #824 (October 2026), printed p. 20 / PDF p. 21, Theorem 3.6

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