浴中奇思：计算熵

凌晨，睡不着，胡思乱想。阅读本文需要基础微积分或者基础计算机科学或者基础密码学知识。

现代密码学很多概念可以分成“完美的”、“统计意义上的”和“计算上的”三个版本。例如对于分布 $D_1,D_2$（实际上应该是 ensemble，也就是分布的序列，但这里依照密码学惯例省略下标，或者说安全参数 $k$），它们的“不可区分性”可以是完美的、统计意义上的或者计算上的。用 $\Delta\left({{\cdot},{\cdot}}\right)$ 表示两个分布的统计距离，那么：

• $D_1,D_2$ 完美不可区分，当且仅当 $\Delta\left({D_1,D_2}\right)=0$；
• $D_1,D_2$ 统计意义上不可区分，当且仅当 $\Delta\left({D_1,D_2}\right)$ 是 $k$ 的可忽略函数；
• $D_1,D_2$ 计算上不可区分，当且仅当对所有（定义取一致或非一致） P.P.T. T.M. $D:{D_1\cup D_2}\to{\left\{{0,1}\right\}}$ 有 $\Delta\left({D\left(D_1\right),D\left(D_2\right)}\right)$ 是可忽略函数。

现在考虑随机数生成器 $G:S\to T$，那么 $G$ （计算上）安全（非密码学语境下也说是“密码学安全”）当且仅当 $G\left(U_S\right),U_T$ 计算上不可区分（$U_X$ 表示 $X$ 上的均匀分布）。

以上是课本知识。“计算上不可区分”的意义大概就是说对于多项式选手（并非术语）来说，它们看不出来两个分布的区别。

Okay，也就是说如果我有一个安全的随机数生成器 $G:{\left\{{0,1}\right\}}^n\to{\left\{{0,1}\right\}}^{n+1}$，那么 $G$ 的输出看起来和随机的 $n+1$ 位 0-1 串没有什么不同。

我们知道度量一个分布编码长度的方式是使用 Shannon 定义的 信息熵。对于一个集合，它上的均匀分布的熵正是它势的对数。

分布的完美不可区分性或统计意义上不可区分性，都是其信息论性质；计算上不可区分性是引入了复杂性理论之后导出的性质。

熵是一个分布的信息论性质，那么引入复杂性理论是否可以导出“计算熵”？

继续用之前提到的安全随机数生成器 $G$，记 $B=\left\{{0,1}\right\}$。$B^{n+1}$ 上均匀分布的熵是 $n+1$ 位。既然 $U_{B^{n+1}}$ 和 $G\left(U_{B^n}\right)$ 是不可区分的，我们自然希望这两者的“计算熵”是相等的。

不难想出一个 toy 级别的计算熵的定义的思路：考虑一个分布 $D$，我们要求多项式时间的算法 $A,B$，这里要求编码器输入来自 $D$ 的元素，输出是 0-1 串，解码器需要把 0-1 串变回原先来自 $D$ 的元素；考虑编码器的输出长度，它应该就对应了“计算熵”的概念；显然诸选项里长度“最小者”应当认为是 $D$ 的“计算熵”。定义的细节还有待考虑，比如可能可以要求可忽略函数概率的错误之类的。

思考告一段落。于是我搜了一下学界有没有已经提出过这个概念的……然后我就看到了姚先生的名字。

Andrew C. Yao. 1982. Theory and application of trapdoor functions. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (SFCS '82). IEEE Computer Society, Washington, DC, USA, 80-91. DOI=http://dx.doi.org/10.1109/SFCS.1982.95

……说不定我是看姚先生的某些介绍的时候看到过“计算熵”这个词（例如可能从 这篇报道 里面见过“计算熵”这个词），然后现在突然蹦进脑子里——我永远不知道我是独立想到了还是潜意识里面已经见过了，好伤心啊！

当然，即使我是独立想到的，希望自己比姚先生生得早也是没什么意义的——如果不是进入了姚班，我可能并不会去想这个玩意儿。