Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 12 — statistical lossiness of the Section C.2 LTDHF

Open
TrapdoorHCF.CCA2.Supplement.lemma_12

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

cryptographyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1public-key-encryptiontrapdoor-hardcore-functions

Let l:N→Nl:\mathbb N\to\mathbb Nl:N→N and let PPP be a lossy public-key encryption scheme that satisfies ciphertext lossiness for messages in {0,1}l(λ)\{0,1\}^{l(\lambda)}{0,1}l(λ) (Definition 7). Then the Section C.2 function LTDHFl(P)\mathrm{LTDHF}_l(P)LTDHFl​(P), with input x=m∥rx=m\Vert rx=m∥r, Eval(pk,x)=Enc(pk,m;r)\mathrm{Eval}(pk,x)=\mathrm{Enc}(pk,m;r)Eval(pk,x)=Enc(pk,m;r) and hEval(pk,x)=m\mathrm{hEval}(pk,x)=mhEval(pk,x)=m, is statistically lossy: there is a negligible ε\varepsilonε such that for every λ\lambdaλ and every lossy key pkpkpk in the support of Genlossy(1λ)\mathrm{Gen}_{lossy}(1^\lambda)Genlossy​(1λ),

Δ((Eval(pk,X),hEval(pk,X)), (Eval(pk,X),U))≤ε(λ),\Delta\bigl((\mathrm{Eval}(pk,X),\mathrm{hEval}(pk,X)),\ (\mathrm{Eval}(pk,X),U)\bigr)\le\varepsilon(\lambda),Δ((Eval(pk,X),hEval(pk,X)), (Eval(pk,X),U))≤ε(λ),

with XXX uniform on DλD_\lambdaDλ​ and U←{0,1}l(λ)U\leftarrow\{0,1\}^{l(\lambda)}U←{0,1}l(λ) 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

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me