Lemma 8 — ciphertext lossiness of the Section C.1 scheme
OpenTrapdoorHCF.CCA2.Supplement.lemma_8cryptographyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1public-key-encryptiontrapdoor-hardcore-functions
Let and let be a lossy trapdoor hardcore function that is statistically lossy with hardcore length (Definition 15). Then the Section C.1 scheme , whose encryption is with , is ciphertext lossy: there is a negligible such that for every , every lossy public key in the support of and all messages ,
with independent. This is the ciphertext-lossiness part of Theorem 10.
Differences from the source:
- generalization: the Section C.1 standing assumption: a perfectly correct and secure (efficient) LTDHF → only statistical lossiness of T is assumed; no correctness, mode indistinguishability or efficiency; reason: the lemma is a statement about laws under lossy keys and the proof uses only Definition 15; every LTDHF of the source satisfies the weaker hypothesis
- reading: Enc(pk, m0; X0) ≈s Enc(pk, m1; X1) for every lambda, lossy key and messages → one negligible bound epsilon(lambda) uniform over lambda, lossy keys and messages, i.e. Definition 7 ciphertext lossiness; reason: SUPPLEMENT.md decision S4: this is what the proof gives (twice the Definition 15 bound), what Theorem 10 needs, and the stronger of the possible readings of a per-key ≈s
- generalization: uniform sampling from efficiently recognizable input spaces D_lambda → polynomial-time input samplers on uniform coins, with the input space their range and no recognizability condition; reason: base paper.md decision 5; every source input space is an instance, so the hypothesis class only grows; the constructions and experiments use only sampling
- 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 8, p.49: ciphertext lossiness of the Section C.1 scheme from statistical lossiness. -/
theorem lemma_8 :
∀ (l : ℕ → ℕ) (T : LTDHF), T.StatLossy l → (lpkeOfLTDHF T).CiphertextLossy 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 8, p.49 (proof p.49), for the construction of Section C.1, pp.47–48