Cslib.Crypto.Protocols.PerfectSecrecy.shannonKeySpace
theoremverifiedformalizationimported Lean
Perfect secrecy requires |K| ≥ |M| (Shannon's theorem).
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.shannonKeySpace [Finite K] (scheme : EncScheme M K C) (h : scheme.PerfectlySecret) : Nat.card K ≥ Nat.card M
- Formalizes
- CSLib, `Cslib.Crypto.Protocols.PerfectSecrecy.shannonKeySpace`
- 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.shannonKeySpace← Cslib.Crypto.Protocols.PerfectSecrecy.shannonKeySpace (Cslib/Crypto/Protocols/PerfectSecrecy/Internal/PerfectSecrecy.lean:115): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- Cslib.Crypto.Protocols.PerfectSecrecy.ciphertextIndist_of_perfectlySecretPerfect secrecy implies ciphertext indistinguishability.
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.ciphertextDistThe distribution of
Enc_K(m)whenK ← Gen. - 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.encrypt_key_injectiveIf each message maps to a key that encrypts it to a common ciphertext, then the key assignment is injective (by correctness of decryption).
- 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…
- Used by 1
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.perfectlySecret_keySpace_gePerfect secrecy requires
|K| ≥ |M|([KatzLindell2020], Theorem 2.12).
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.perfectlySecret_keySpace_gePerfect secrecy requires
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 requires `|K| ≥ |M|` (Shannon's theorem). -/theorem Cslib.Crypto.Protocols.PerfectSecrecy.shannonKeySpace [Finite K] (scheme : EncScheme M K C) (h : scheme.PerfectlySecret) : Nat.card K ≥ Nat.card M := by classical have hci := ciphertextIndist_of_perfectlySecret scheme h by_cases hM : IsEmpty M; · simp obtain ⟨m₀⟩ := not_isEmpty_iff.mp hM obtain ⟨c₀, hc₀⟩ := (scheme.ciphertextDist m₀).support_nonempty have key_exists : ∀ m, ∃ k ∈ scheme.gen.support, c₀ ∈ (scheme.enc k m).support := by intro m exact (PMF.mem_support_bind_iff _ _ _).mp (show c₀ ∈ (scheme.ciphertextDist m).support by rw [hci m m₀]; exact hc₀) choose f hf_mem hf_enc using key_exists exact Nat.card_le_card_of_injective f (encrypt_key_injective scheme f c₀ hf_mem hf_enc)