Theorem 3.4 — Public-key encryption from unmarked planting and noisy XOR
OpenExpandingCodes.PolynomialStretch.Supplement.noisy_xor_pkeFix rational and real satisfying (1), (6) and (7), as specified by the parameter definition. In particular, , and are fixed by the code construction. Assume unmarked Conjecture 3.1 and Conjecture 3.2 at precisely these parameters and the dyadic density.
There exist a bit public-key encryption scheme, fixed polynomial bounds and a constant such that all three algorithms have actual polynomial-time machine implementations, the scheme is semantically secure against nonuniform polynomial-size circuit families, and for every sufficiently large security parameter ,
The error averages over key generation and encryption coins, with failures counted as errors. The adversary sees the entire public key and ciphertext. One threshold works for both bits and every allowed circuit.
This is the first conditional encryption companion theorem; it is not used to prove the published code-construction goal. Efficiency and both security guarantees are conclusions, and no amplification assumption is added.
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.4: conjectures at any one admissible rational parameter choice suffice.
All efficiency, correctness, and security properties are conclusions. -/
theorem noisy_xor_pke (ε C β : ℚ) (δ : ℝ)
(hparams : NoisyParameters ε C β δ)
(hplant : UnmarkedPlanting (ε : ℝ) (arity (ε : ℝ))
(rowCount (dimension (ε : ℝ))) C β δ)
(hxor : RandomXOR (ε : ℝ) (arity (ε : ℝ)) C β δ) :
SecurePKEExists := by sorry
end ExpandingCodes.PolynomialStretch.Supplement