Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.perfectlySecret_keySpace_ge
theoremverifiedformalizationimported Lean
Perfect secrecy requires |K| ≥ |M| ([KatzLindell2020], Theorem 2.12).
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in universe u in variable {M K C : Type u} in theorem Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.perfectlySecret_keySpace_ge [Finite K] (scheme : EncScheme M K C) (h : scheme.PerfectlySecret) : Nat.card K ≥ Nat.card M
- Formalizes
- CSLib, `Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.perfectlySecret_keySpace_ge`
- 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.EncScheme.perfectlySecret_keySpace_ge← Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.perfectlySecret_keySpace_ge (Cslib/Crypto/Protocols/PerfectSecrecy/Basic.lean:46): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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.shannonKeySpacePerfect secrecy requires
|K| ≥ |M|(Shannon's theorem). - 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.EncSchemeA private-key encryption scheme over message space
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in universe u in variable {M K C : Type u} in /-- Perfect secrecy requires `|K| ≥ |M|` ([KatzLindell2020], Theorem 2.12). -/ theorem Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.perfectlySecret_keySpace_ge [Finite K] (scheme : EncScheme M K C) (h : scheme.PerfectlySecret) : Nat.card K ≥ Nat.card M := PerfectSecrecy.shannonKeySpace scheme h