AFTD Auto-Formalizing Theoretical Domains

Cslib.Crypto.Protocols.PerfectSecrecy.ciphertextIndist_of_perfectlySecret

theoremverifiedformalizationimported Lean

Perfect secrecy implies ciphertext indistinguishability.

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.ciphertextIndist_of_perfectlySecret (scheme : EncScheme M K C)
    (h : scheme.PerfectlySecret) :
    scheme.CiphertextIndist
Formalizes
CSLib, `Cslib.Crypto.Protocols.PerfectSecrecy.ciphertextIndist_of_perfectlySecret`
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 9
Used by 2

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 implies ciphertext indistinguishability. -/theorem Cslib.Crypto.Protocols.PerfectSecrecy.ciphertextIndist_of_perfectlySecret (scheme : EncScheme M K C)    (h : scheme.PerfectlySecret) :    scheme.CiphertextIndist := by  classical  rw [perfectlySecret_iff_indep] at h  intro m₀ m₁; ext c  have hs : ({m₀, m₁} : Finset M).Nonempty := ⟨m₀, Finset.mem_insert_self ..⟩  set μ := PMF.uniformOfFinset _ hs  suffices key : ∀ m ∈ ({m₀, m₁} : Finset M),      scheme.ciphertextDist m c = scheme.marginalCiphertextDist μ c by    exact (key m₀ (by simp)).trans (key m₁ (by simp)).symm  intro m hm  have hne := (PMF.mem_support_uniformOfFinset_iff hs m).mpr hm  have hne_top := ne_top_of_le_ne_top one_ne_top (PMF.coe_le_one μ m)  exact (ENNReal.mul_right_inj hne hne_top).mp (by rw [← jointDist_eq]; exact h μ m c)
See it in the graphDiscuss this resultChallenge it