Cslib.Crypto.Protocols.PerfectSecrecy.indep_of_ciphertextIndist
theoremverifiedformalizationimported Lean
Ciphertext indistinguishability implies message-ciphertext independence.
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.indep_of_ciphertextIndist (scheme : EncScheme M K C) (h : scheme.CiphertextIndist) (msgDist : PMF M) (m : M) (c : C) : scheme.jointDist msgDist (m, c) = msgDist m * scheme.marginalCiphertextDist msgDist c
- Formalizes
- CSLib, `Cslib.Crypto.Protocols.PerfectSecrecy.indep_of_ciphertextIndist`
- 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.indep_of_ciphertextIndist← Cslib.Crypto.Protocols.PerfectSecrecy.indep_of_ciphertextIndist (Cslib/Crypto/Protocols/PerfectSecrecy/Internal/PerfectSecrecy.lean:67): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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.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.Crypto.Protocols.PerfectSecrecy.EncScheme.ciphertextDistThe distribution of
- Used by 1
- Cslib.Crypto.Protocols.PerfectSecrecy.perfectlySecret_of_ciphertextIndistCiphertext indistinguishability implies perfect secrecy.
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/-- Ciphertext indistinguishability implies message-ciphertext independence. -/theorem Cslib.Crypto.Protocols.PerfectSecrecy.indep_of_ciphertextIndist (scheme : EncScheme M K C) (h : scheme.CiphertextIndist) (msgDist : PMF M) (m : M) (c : C) : scheme.jointDist msgDist (m, c) = msgDist m * scheme.marginalCiphertextDist msgDist c := by rw [jointDist_eq]; congr 1 change scheme.ciphertextDist m c = PMF.bind msgDist (fun m' => scheme.ciphertextDist m') c rw [PMF.bind_apply] conv_rhs => arg 1; ext m'; rw [h m' m] rw [ENNReal.tsum_mul_right, PMF.tsum_coe, one_mul]