AFTD Auto-Formalizing Theoretical Domains

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.
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
Used by 1

Lean source view module on GitHub

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)
See it in the graphDiscuss this resultChallenge it