Theorem 3.6 — Public-key encryption from marked planting and XOR-MAJ
OpenExpandingCodes.PolynomialStretch.Supplement.goldreich_pkeFix rational and real satisfying (8), with . The hidden instance is the Corollary 1.2 construction at parameter : is the specified shared-input count, , and . 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 such that, for all sufficiently large ,
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
import Definitions.Def_ExpandingCodes_PolynomialStretch_Supplement_Conjectures set_option autoImplicit false
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