完美保密密钥下界

Shannon 下界说明，若要让同一密文对所有候选明文都保持同等解释空间，同时保证正确解密和完美保密，密钥必须提供至少与消息不确定性相当的随机性；不能用一个短、可重复的秘密无条件隐藏任意更长消息。证明利用 $M$ 可由 $(C,K)$ 恢复而 $C$ 与 $M$ 独立，把条件熵链合并成 $H(K)\ge H(M)$。这不是对计算安全加密的限制，伪随机性正是用困难假设绕开信息论要求。

均匀 $n$ bit 消息的熵为 $n$，任何一次性、完美保密且零错误的方案都需至少 $n$ bit 密钥熵；OTP 使用均匀 $n$ bit 密钥达到等号。若消息只取两个高度偏置值，熵下界可小于表示长度，但更强的“对所有消息先验或每对明文”版本还会约束密钥空间基数。伪随机生成器从短种子扩展密钥流只能提供计算安全，不能绕过信息论下界获得完美保密。

密钥文件长度大不等于熵大：可预测或重复生成的 $n$ bit 串可能只有很低熵。压缩消息后再 OTP 可以把密钥需求降到压缩长度，但压缩模型和长度本身可能泄露信息。

这个结果解释了为什么完美保密难以大规模部署，并划清信息论安全与基于计算假设安全的边界。完美保密公理库完美保密Perfect secrecy · Information-theoretic security对每种消息先验，观察密文都不改变消息分布的无条件安全定义。 提供独立性条件，熵公理库Shannon 熵Shannon entropy · Information entropy随机变量不确定性的平均信息量，以最优编码所需位数为基本解释。 提供资源计量，一次一密公理库一次一密One-time pad · Vernam cipher使用与消息等长的均匀随机密钥并只使用一次的异或加密方案。 达到界；伪随机生成器公理库伪随机生成器Pseudorandom generator · PRG把短均匀种子扩展为计算上不可与均匀串区分的长输出。 与流密码把短密钥扩成长密钥流，只获得计算安全，而非反驳该下界。