Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Under perfect secrecy, H(M)≤H(K)H(M) \le H(K)H(M)≤H(K)

Proved
ShannonSecrecy.perfect_secrecy_entropy_msg_le_entropy_key

by LG · Sep 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

cryptographyentropyinformation-theory

Shannon 1949, §10, p. 682. There is a limit to what can be obtained with a given uncertainty in key: the amount of uncertainty that can be introduced into the solution cannot be greater than the key uncertainty.

In a finite secrecy system with perfect secrecy, the entropy of the message is at most the entropy of the key:

H(M)  =  −∑MP(M)log⁡P(M)  ≤  −∑KP(K)log⁡P(K)  =  H(K),H(M) \;=\; -\sum_{M} P(M)\log P(M) \;\le\; -\sum_{K} P(K)\log P(K) \;=\; H(K),H(M)=−M∑​P(M)logP(M)≤−K∑​P(K)logP(K)=H(K),

for every a priori message distribution P(⋅)P(\cdot)P(⋅). Shannon states the principle in §10 in the special case of the perfect systems just constructed, where the message carries at most log⁡n\log nlogn bits and "this information can be concealed completely only if the key uncertainty is at least log⁡n\log nlogn", and announces it as the general principle that recurs throughout the paper.

Combined with the key-counting result, this is the quantitative form of the one-time-pad constraint: concealing H(M)H(M)H(M) units of message uncertainty costs at least H(M)H(M)H(M) units of key uncertainty.

Formalization Note Entropy is H(q)=∑a−q(a)log⁡q(a)H(q) = \sum_a -q(a)\log q(a)H(q)=∑a​−q(a)logq(a) with the natural logarithm, so both sides are measured in nats; since a change of base multiplies both sides by the same positive constant, the inequality is base-independent. The message distribution is an arbitrary a priori distribution on the finite message set, and the key distribution is the one carried by the system.

Preamble
import Definitions.Def_shannon_secrecy_system
Formal statement
namespace ShannonSecrecy

theorem perfect_secrecy_entropy_msg_le_entropy_key
    {M K E : Type*} [Fintype M] [Fintype K] [Fintype E] [DecidableEq E]
    (C : Cipher M K E) (h : PerfectSecrecy C) (p : M → ℝ) (hp : IsPMF p) :
    entropy p ≤ entropy C.keyProb := by sorry

end ShannonSecrecy
Source
C. E. Shannon, "Communication Theory of Secrecy Systems", Bell System Technical Journal 28(4):656-715, 1949; https://doi.org/10.1002/j.1538-7305.1949.tb00928.x, p. 682 (Part II, §10 Perfect Secrecy, the paragraph on key uncertainty following the entropy definitions)
Read-back

What the Lean code literally says, in plain math · Aristotle (Harmonic) — NON-BLIND: same agent that drafted the statement

Provenance note — this read-back is NOT independent testimony. It is non-blind: it was written by the same agent that drafted the Lean statement it describes, working from the source paper and from its own formalization intent, and not by an independent auditor with a fresh context who saw only the Lean code. It therefore cannot corroborate the faithfulness of the formalization — an agreement between the statement and this read-back is self-agreement. Treat it as an annotation by the author, and obtain a blind read-back before relying on it during audit or moderation.

Let MMM, KKK, EEE be finite types with decidable equality on EEE, and let CCC be a cipher on them: injective maps Tk:M→ET_k : M \to ETk​:M→E for k∈Kk \in Kk∈K, weights P(k)≥0P(k) \ge 0P(k)≥0 with ∑kP(k)=1\sum_{k} P(k) = 1∑k​P(k)=1. Assume CCC has the perfect-secrecy property (for every PMF on MMM, every cryptogram of nonzero total probability, and every message, the a posteriori probability equals the a priori one). Let p:M→Rp : M \to \mathbb{R}p:M→R satisfy p(m)≥0p(m) \ge 0p(m)≥0 for all mmm and ∑mp(m)=1\sum_m p(m) = 1∑m​p(m)=1.

The conclusion is the inequality of real numbers

∑m∈M(−p(m)ln⁡p(m))  ≤  ∑k∈K(−P(k)ln⁡P(k)),\sum_{m \in M} \big(-p(m)\ln p(m)\big) \;\le\; \sum_{k \in K} \big(-P(k)\ln P(k)\big),m∈M∑​(−p(m)lnp(m))≤k∈K∑​(−P(k)lnP(k)),

where the logarithm is natural and each summand is the function x↦−xln⁡xx \mapsto -x\ln xx↦−xlnx evaluated at the corresponding probability, with the convention that this function is 000 at x=0x = 0x=0. On the left the sum ranges over the message type with the given distribution ppp; on the right over the key type with the cipher's own key weights.

Degenerate readings permitted by the statement: if MMM is empty there is no such ppp and the claim is vacuous; if MMM is a single point the left side is 000; keys of probability zero contribute 000 to the right-hand sum. The inequality is not strict, and the base of the logarithm is fixed to eee, so the two entropies are in nats.

Human review
  • Endorsed by Shuze Chen · Sep 23, 2026

  • Endorsed by LG · Sep 23, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me