Cslib.Crypto.Protocols.PerfectSecrecy.otp_perfectlySecret
theoremverifiedformalizationimported Lean
The one-time pad is perfectly secret ([KatzLindell2020], Theorem 2.10).
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in theorem Cslib.Crypto.Protocols.PerfectSecrecy.otp_perfectlySecret (l : ℕ) : (otp l).PerfectlySecret
- Formalizes
- CSLib, `Cslib.Crypto.Protocols.PerfectSecrecy.otp_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.Cslib.Crypto.Protocols.PerfectSecrecy.otp_perfectlySecret← Cslib.Crypto.Protocols.PerfectSecrecy.otp_perfectlySecret (Cslib/Crypto/Protocols/PerfectSecrecy/OneTimePad.lean:45): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.ciphertextDistThe distribution of
Enc_K(m)whenK ← Gen. - 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.EncSchemeA private-key encryption scheme over message space
M, key spaceK, and ciphertext spaceC([KatzLindell2020], Definition 2.1). - Cslib.Crypto.Protocols.PerfectSecrecy.OTP.bitVecFintypeCslib.Crypto.Protocols.PerfectSecrecy.OTP.bitVecFintype
- Cslib.Probability.PMF.posteriorDist_applyCslib.Probability.PMF.posteriorDist_apply
- 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.PerfectlySecretAn encryption scheme is perfectly secret if the posterior message distribution equals the prior for every ciphertext with positive…
- Cslib.Crypto.Protocols.PerfectSecrecy.OTP.otp_ciphertextDist_eq_uniformThe ciphertext distribution of the OTP is uniform, regardless of the message.
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.ciphertextDistThe distribution of
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 in/-- The one-time pad is perfectly secret ([KatzLindell2020], Theorem 2.10). -/theorem Cslib.Crypto.Protocols.PerfectSecrecy.otp_perfectlySecret (l : ℕ) : (otp l).PerfectlySecret := (EncScheme.perfectlySecret_iff_ciphertextIndist _).mpr fun m₀ m₁ => by simp only [EncScheme.ciphertextDist, otp] exact (OTP.otp_ciphertextDist_eq_uniform l m₀).trans (OTP.otp_ciphertextDist_eq_uniform l m₁).symm