Lemma 12 — statistical lossiness of the Section C.2 LTDHF
OpenTrapdoorHCF.CCA2.Supplement.lemma_12cryptographyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1public-key-encryptiontrapdoor-hardcore-functions
Let and let be a lossy public-key encryption scheme that satisfies ciphertext lossiness for messages in (Definition 7). Then the Section C.2 function , with input , and , is statistically lossy: there is a negligible such that for every and every lossy key in the support of ,
with uniform on and independent. This is the statistical-lossiness part of Theorem 11.
Differences from the source:
- generalization: the Section C.2 standing assumption: a perfectly correct and secure (efficient) lossy PKE with message space {0,1}^{l(lambda)} → only ciphertext lossiness of P for messages of length l(lambda) is assumed; no correctness, mode indistinguishability, efficiency or public length; reason: the lemma states exactly this hypothesis and is a statement about laws; every scheme of Section C.2 satisfies it
- encoding: every lossy public key in Supp(KGen_los(1^lambda)) → losKeyGen lambda r for every lossy key coin vector r; reason: the same set of keys
- 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
- encoding: strings, pairs, inputs x = m||r, randomness and the failure symbol → bit strings, tuple-coded pairs, explicit uniform finite coin vectors, and Option for failure; reason: injective data codes; they change no instance of the source experiments
Preamble
import Mathlib import Definitions.Def_TrapdoorHCF_CCA2_Supplement_Lossy open QAlgorithms.Complexity set_option autoImplicit false
Formal statement
namespace TrapdoorHCF.CCA2.Supplement
open TrapdoorHCF.CCA2
/-- Lemma 12, p.52: statistical lossiness of the Section C.2 LTDHF from ciphertext lossiness. -/
theorem lemma_12 :
∀ (l : ℕ → ℕ) (P : LPKE), P.CiphertextLossy l → (ltdhfOfLPKE l P).StatLossy l := 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 12, p.52 (proof p.52), for the construction of Section C.2, p.50