Under perfect secrecy,
ProvedShannonSecrecy.perfect_secrecy_entropy_msg_le_entropy_keyShannon 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:
for every a priori message distribution . Shannon states the principle in §10 in the special case of the perfect systems just constructed, where the message carries at most bits and "this information can be concealed completely only if the key uncertainty is at least ", 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 units of message uncertainty costs at least units of key uncertainty.
Formalization Note Entropy is 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.
import Definitions.Def_shannon_secrecy_system
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 ShannonSecrecyRead-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 , , be finite types with decidable equality on , and let be a cipher on them: injective maps for , weights with . Assume has the perfect-secrecy property (for every PMF on , every cryptogram of nonzero total probability, and every message, the a posteriori probability equals the a priori one). Let satisfy for all and .
The conclusion is the inequality of real numbers
where the logarithm is natural and each summand is the function evaluated at the corresponding probability, with the convention that this function is at . On the left the sum ranges over the message type with the given distribution ; on the right over the key type with the cipher's own key weights.
Degenerate readings permitted by the statement: if is empty there is no such and the claim is vacuous; if is a single point the left side is ; keys of probability zero contribute to the right-hand sum. The inequality is not strict, and the base of the logarithm is fixed to , so the two entropies are in nats.
Confirmed by the mission captain (proposal self-audit).