Lemma 11 — pairwise closeness implies near-independence
OpenTrapdoorHCF.CCA2.Supplement.lemma_11cryptographyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1public-key-encryptiontrapdoor-hardcore-functions
Let be a finite nonempty set, let be any set, and let be probability distributions on with for all . Let be independent and uniform on , and let . Then
The statement has no security parameter. Lemma 12 applies it to the ciphertext distributions of a lossy public key.
Differences from the source:
- reading: (C, M) ≈s (C, U) → Delta((C, M), (C, U)) <= epsilon with the same epsilon; reason: the lemma has no security parameter; this is the last display of its proof (p.52) and the form Lemma 12 quotes ("More precisely, Delta((C,M),(C,U)) <= epsilon(lambda)")
- encoding: a finite family of distributions and uniform M, U → a Fintype, Nonempty index type with PMF.uniformOfFintype; reason: a uniform label on an empty family is undefined, so nonemptiness only excludes an undefined case
- encoding: statistical distance (1/2) sum over omega of |Pr[X = omega] - Pr[Y = omega]| → (1/2) times the real tsum over all outcomes of |p(omega) - q(omega)| for PMFs on an arbitrary type; reason: the series is absolutely summable for PMFs, so this is the same number; no finiteness of the outcome space is assumed
Preamble
import Mathlib import Definitions.Def_TrapdoorHCF_CCA2_Supplement_CPA open QAlgorithms.Complexity set_option autoImplicit false
Formal statement
namespace TrapdoorHCF.CCA2.Supplement
open TrapdoorHCF.CCA2
/-- Lemma 11, pp.51–52: for a finite nonempty family `{D_m}` with pairwise distance at most `ε`,
`M, U` independent uniform labels and `C ← D_M`, `Δ((C,M), (C,U)) ≤ ε` (p.52, last display). -/
theorem lemma_11 {ι α : Type} [Fintype ι] [Nonempty ι] (D : ι → PMF α) (ε : ℝ)
(hD : ∀ m m' : ι, sd (D m) (D m') ≤ ε) :
sd ((PMF.uniformOfFintype ι).bind fun m => (D m).map fun c => (c, m))
(((PMF.uniformOfFintype ι).bind D).bind fun c =>
(PMF.uniformOfFintype ι).map fun u => (c, u)) ≤ ε := by sorry
end TrapdoorHCF.CCA2.Supplement
Source
Kanad Chakravarti, Shreyas Gupta, Bhavana Kanukurthi, Girisha Shankar, Trapdoors Beyond Inversion: Recoverable Information in Public-Key Cryptography, STOC 2027 submission #571 (October 2026; unrefereed), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/571.pdf, Lemma 11, p.51 (proof pp.51–52)