完美保密密钥下界

密文没有消除的不确定性，密钥必须消除 ​

仅看密文时，攻击者对明文的知识不应改变；给合法接收者再补上密钥，明文又必须完全确定。两句要求可以分别写成

它们一相减，就得到一个短证明：

中间的条件互信息 $I(M;K\mid C)$，表示已经知道密文后，密钥还能提供多少关于明文的信息；它最多等于密钥在此条件下剩余的熵。这正是条件熵理路条件熵Conditional entropy已知一个随机变量后另一个随机变量剩余不确定性的平均值。把直觉变成下界的地方。

注意证明没有假设明文均匀，也没有要求加密确定。只要接收者凭 $K,C$ 必须恢复 $M$，加密时额外抛出的、没有另行秘密共享的随机硬币就不会让这个下界消失。

密钥个数为何也不能太少 ​

把明文在整个 $\mathcal{M}$ 上取为均匀分布，便有 $H(M)={\log }_2|\mathcal{M}|$。再利用 $H(K)\le {\log }_2|\mathcal{K}|$，得到密钥空间的基数下界。

也可以固定一个可能出现的密文 $c$ 直接计数。完美保密要求每个候选明文 $m$ 都有产生 $c$ 的可能；否则看到 $c$ 就排除了某些明文。每个候选 $m$ 至少需要一个能把 $c$ 解成它的密钥，而零错误解密不允许同一个密钥把同一个 $c$ 解成两个不同明文。因此至少需要 $|\mathcal{M}|$ 个密钥。这一论证把“候选不能被排除”和“接收者必须唯一恢复”放在同一幅图景里。

一次一密恰好达到下界 ​

对三比特消息，一次一密理路一次一密One-time pad使用与消息等长的均匀随机密钥并只使用一次的异或加密方案。取独立均匀密钥 $K\in \{0,1{\}}^3$，令 $C=M\oplus K$。若观察到 $C=000$，八个候选明文仍都可能：候选 $m$ 对应唯一密钥 $k=m$，且每个密钥概率都是 $1/8$。

这不是说“观察密文后明文一定均匀”。若明文原本偏向 000，后验仍保持同样的偏向；密文没有额外改变它。密钥均匀和明文均匀承担不同角色：前者是这个方案的安全条件，后者只是证明最坏消息空间下界时可选的测试分布。

有偏消息不自动兑现更短的固定密钥 ​

若某个先验下 $H(M)<{\log }_2|\mathcal{M}|$，不等式 $H(K)\ge H(M)$ 本身只是一个必要条件，并没有构造出这么短的密钥方案。事实上，对有限消息空间，若一个固定先验对每个消息都赋正概率，且该先验下 $M,C$ 独立，那么每个消息诱导的密文分布已经相同；同一方案于是也对均匀先验安全，仍须满足更强的 $H(K)\ge {\log }_2|\mathcal{M}|$。

压缩、可变长编码或允许忽略小概率消息可以改变模型，但要重新核对是否仍要求每条消息零错误恢复，以及密文长度是否暴露信息。不能把无损压缩的平均码长结论直接当成固定长度完美保密的可达密钥长度。

重复使用和伪随机扩展改变了什么 ​

两条消息若重复使用同一段一次一密密钥，便有

即使单独观察每一条密文都像随机串，联合观察仍泄露两条明文的关系。若要求整组消息完美保密，就应把 $(M_1,M_2)$ 当作联合明文应用下界，而不能对每条消息各用一次单消息论证。

流密码理路流密码Stream cipher以密钥、nonce 与流位置解释异或加密，区分计算伪随机性、密钥流复用、同步和认证。把短种子扩展成长密钥流，追求的是有计算限制的攻击者无法区分，而不是长流真的获得了更多熵。一个确定性生成器的输出熵至多等于种子熵；它绕开的不是 Shannon 证明，而是把安全目标改成了计算安全。

这个下界给密钥分发提供了明确账本：若目标是任意消息的零错误、信息论完美保密，预共享秘密的熵必须覆盖需要隐藏的消息规模。增加公开随机性、重复运行公开算法或更换复杂编码，都不能替代这份秘密资源。

下界也只讨论保密，不自动提供完整性。一次一密达到最优密钥长度，却允许攻击者按位翻转明文；认证需要另外的条件和机制。