Cslib.Crypto.Protocols.PerfectSecrecy.perfectlySecret_iff_indep
theoremverifiedformalizationimported Lean
Perfect secrecy is equivalent to message-ciphertext independence. The two formulations are related by multiplying/dividing by marginal(c).
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open PMF ENNReal in universe u in variable {M K C : Type u} in theorem Cslib.Crypto.Protocols.PerfectSecrecy.perfectlySecret_iff_indep (scheme : EncScheme M K C) : scheme.PerfectlySecret ↔ ∀ (msgDist : PMF M) (m : M) (c : C), scheme.jointDist msgDist (m, c) = msgDist m * scheme.marginalCiphertextDist msgDist c
- Formalizes
- CSLib, `Cslib.Crypto.Protocols.PerfectSecrecy.perfectlySecret_iff_indep`
- Lean proof
- By Samuel Schlesinger, from github.com/leanprover/cslib at
3951377e5a3f(Copyright (c) 2026 Samuel Schlesinger. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.Cslib.Crypto.Protocols.PerfectSecrecy.perfectlySecret_iff_indep← Cslib.Crypto.Protocols.PerfectSecrecy.perfectlySecret_iff_indep (Cslib/Crypto/Protocols/PerfectSecrecy/Internal/PerfectSecrecy.lean:44): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.marginalCiphertextDistMarginal ciphertext distribution given a message prior.
- Cslib.Crypto.Protocols.PerfectSecrecy.EncSchemeA private-key encryption scheme over message space
M, key spaceK, and ciphertext spaceC([KatzLindell2020], Definition 2.1). - Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.jointDistJoint distribution of
(M, C)given a message prior. - Cslib.Probability.PMF.posteriorDist_applyCslib.Probability.PMF.posteriorDist_apply
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.posteriorMsgDist_applyCslib.Crypto.Protocols.PerfectSecrecy.EncScheme.posteriorMsgDist_apply
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.PerfectlySecretAn encryption scheme is perfectly secret if the posterior message distribution equals the prior for every ciphertext with positive…
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.posteriorMsgDistThe posterior message distribution
Pr[M | C = c]as a probability distribution, given a message prior and a ciphertext in the support of… - Cslib.Crypto.Protocols.PerfectSecrecy.jointDist_tsum_fstSumming the joint distribution over messages gives the marginal ciphertext distribution.
- Used by 2
- Cslib.Crypto.Protocols.PerfectSecrecy.ciphertextIndist_of_perfectlySecretPerfect secrecy implies ciphertext indistinguishability.
- Cslib.Crypto.Protocols.PerfectSecrecy.perfectlySecret_of_ciphertextIndistCiphertext indistinguishability implies perfect secrecy.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen PMF ENNReal inuniverse u invariable {M K C : Type u} in/-- Perfect secrecy is equivalent to message-ciphertext independence. The two formulations are related by multiplying/dividing by `marginal(c)`. -/theorem Cslib.Crypto.Protocols.PerfectSecrecy.perfectlySecret_iff_indep (scheme : EncScheme M K C) : scheme.PerfectlySecret ↔ ∀ (msgDist : PMF M) (m : M) (c : C), scheme.jointDist msgDist (m, c) = msgDist m * scheme.marginalCiphertextDist msgDist c := by constructor · intro h msgDist m c by_cases hc : (scheme.marginalCiphertextDist msgDist) c = 0 · have := ENNReal.tsum_eq_zero.mp ((jointDist_tsum_fst scheme msgDist c).trans hc) m rw [this, hc, mul_zero] · have hne_top := ne_top_of_le_ne_top one_ne_top (PMF.coe_le_one (scheme.marginalCiphertextDist msgDist) c) have := DFunLike.congr_fun (h msgDist c ((PMF.mem_support_iff _ _).mpr hc)) m simp only [EncScheme.posteriorMsgDist_apply] at this rw [← this, ENNReal.div_mul_cancel hc hne_top] · intro h msgDist c hc; ext m simp only [EncScheme.posteriorMsgDist_apply] rw [h msgDist m c, ENNReal.mul_div_cancel_right ((PMF.mem_support_iff _ _).mp hc) (ne_top_of_le_ne_top one_ne_top (PMF.coe_le_one _ c))]