Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme
structureimported Lean
A private-key encryption scheme over message space M, key space K, and ciphertext space C ([KatzLindell2020], Definition 2.1).
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in structure Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme (Message Key Ciphertext : Type*)
- Defined in
- CSLib, `Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme`
- 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← Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme (Cslib/Crypto/Protocols/PerfectSecrecy/Encryption.lean:38): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Used by 20
- 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.marginalCiphertextDistMarginal ciphertext distribution given a message prior.
- 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.EncScheme.CiphertextIndistCiphertext indistinguishability: the ciphertext distribution is the same for all messages ([KatzLindell2020], Lemma 2.5).
- Cslib.Crypto.Protocols.PerfectSecrecy.otp_perfectlySecretThe one-time pad is perfectly secret ([KatzLindell2020], Theorem 2.10).
- Cslib.Crypto.Protocols.PerfectSecrecy.perfectlySecret_of_ciphertextIndistCiphertext indistinguishability implies perfect secrecy.
- Cslib.Crypto.Protocols.PerfectSecrecy.shannonKeySpacePerfect secrecy requires
|K| ≥ |M|(Shannon's theorem). - 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.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.Crypto.Protocols.PerfectSecrecy.indep_of_ciphertextIndistCiphertext indistinguishability implies message-ciphertext independence.
- Cslib.Crypto.Protocols.PerfectSecrecy.jointDist_eqThe joint distribution at
(m, c)equalsmsgDist m * ciphertextDist m c. - Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.ofPureBuild an encryption scheme from deterministic pure encryption/decryption where decryption is a left inverse of encryption for every key.
- Cslib.Crypto.Protocols.PerfectSecrecy.otpThe one-time pad over
l-bit strings. Encryption and decryption are XOR ([KatzLindell2020], Construction 2.9). - 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.
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.perfectlySecret_keySpace_gePerfect secrecy requires
|K| ≥ |M|([KatzLindell2020], Theorem 2.12).
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in /-- A private-key encryption scheme over message space `M`, key space `K`, and ciphertext space `C` ([KatzLindell2020], Definition 2.1). -/ structure Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme (Message Key Ciphertext : Type*) where /-- Probabilistic key generation. -/ gen : PMF Key /-- (Possibly randomized) encryption. -/ enc (key : Key) (message : Message) : PMF Ciphertext /-- Deterministic decryption. -/ dec (key : Key) (ciphertext : Ciphertext) : Message /-- Decryption inverts encryption for all keys in the support of `gen`. -/ correct : ∀ key, key ∈ gen.support → ∀ message ciphertext, ciphertext ∈ (enc key message).support → dec key ciphertext = message