Cslib.Crypto.Protocols.PerfectSecrecy.ciphertextIndist_of_perfectlySecret
theoremverifiedformalizationimported Lean
Perfect secrecy implies ciphertext indistinguishability.
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.ciphertextIndist_of_perfectlySecret (scheme : EncScheme M K C) (h : scheme.PerfectlySecret) : scheme.CiphertextIndist
- Formalizes
- CSLib, `Cslib.Crypto.Protocols.PerfectSecrecy.ciphertextIndist_of_perfectlySecret`
- 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.ciphertextIndist_of_perfectlySecret← Cslib.Crypto.Protocols.PerfectSecrecy.ciphertextIndist_of_perfectlySecret (Cslib/Crypto/Protocols/PerfectSecrecy/Internal/PerfectSecrecy.lean:87): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.ciphertextDistThe distribution of
Enc_K(m)whenK ← Gen. - Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.marginalCiphertextDistMarginal ciphertext distribution given a message prior.
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.CiphertextIndistCiphertext indistinguishability: the ciphertext distribution is the same for all messages ([KatzLindell2020], Lemma 2.5).
- 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.perfectlySecret_iff_indepPerfect secrecy is equivalent to message-ciphertext independence. The two formulations are related by multiplying/dividing by
marginal(c). - Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.jointDistJoint distribution of
(M, C)given a message prior. - Cslib.Crypto.Protocols.PerfectSecrecy.jointDist_eqThe joint distribution at
(m, c)equalsmsgDist m * ciphertextDist m c. - Cslib.Probability.PMF.posteriorDist_applyCslib.Probability.PMF.posteriorDist_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.ciphertextDistThe distribution of
- Used by 2
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.perfectlySecret_iff_ciphertextIndistA scheme is perfectly secret iff the ciphertext distribution is independent of the plaintext ([KatzLindell2020], Lemma 2.5).
- Cslib.Crypto.Protocols.PerfectSecrecy.shannonKeySpacePerfect secrecy requires
|K| ≥ |M|(Shannon's theorem).
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 implies ciphertext indistinguishability. -/theorem Cslib.Crypto.Protocols.PerfectSecrecy.ciphertextIndist_of_perfectlySecret (scheme : EncScheme M K C) (h : scheme.PerfectlySecret) : scheme.CiphertextIndist := by classical rw [perfectlySecret_iff_indep] at h intro m₀ m₁; ext c have hs : ({m₀, m₁} : Finset M).Nonempty := ⟨m₀, Finset.mem_insert_self ..⟩ set μ := PMF.uniformOfFinset _ hs suffices key : ∀ m ∈ ({m₀, m₁} : Finset M), scheme.ciphertextDist m c = scheme.marginalCiphertextDist μ c by exact (key m₀ (by simp)).trans (key m₁ (by simp)).symm intro m hm have hne := (PMF.mem_support_uniformOfFinset_iff hs m).mpr hm have hne_top := ne_top_of_le_ne_top one_ne_top (PMF.coe_le_one μ m) exact (ENNReal.mul_right_inj hne hne_top).mp (by rw [← jointDist_eq]; exact h μ m c)